Коды с обнаружением ошибок

Обнаружение и исправление ошибок

В рассмотренных кодах каждый кодовый набор состоит из четырёх двоичных разрядов. Их количество минимально для представления 10 десятичных цифр. Эти коды очень чувствительны к ошибкам, возникающим из-за сбоев в работе аппаратуры или помех в каналах передачи данных. В любой работающей системе всегда существует ненулевая вероятность появления одиночной ошибки. Вероятность появления двух и более ошибок значительно меньше. Рассмотрим обнаружение и исправление одиночных ошибок.

Появление одиночной ошибки в одном из разрядов может привести как к запрещенному, так и к неправильному, но допустимому кодовому набору.

Пример

Код 8421. Исходное число 0110. В результате сбоя появляется 1110- запрещенный кодовый набор или 0100 – допустимый кодовый набор. Последний будет неправильно интерпретирован приемным устройством.

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

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

Таблица 13

Десятичная цифра	BCD код с проверкой на четность 8 4 2 1 р	Код “2 из 5”     0 1 2 4 7
	0 0 0 0 0	0 0 0 1 1
	0 0 0 1 1	1 1 0 0 0
	0 0 1 0 0	1 0 1 0 0
	0 0 1 1 0	0 1 1 0 0
	0 1 0 0 1	1 0 0 1 0
	0 1 0 1 0	0 1 0 1 0
	0 1 1 0 0	0 0 1 1 0
	0 1 1 1 1	1 0 0 0 1
	1 0 0 0 1	0 1 0 0 1
	1 0 0 1 0	0 0 1 0 1

В кодах, приведенных в таблице 13, осуществляется проверка на четность:

BCD код с проверкой на четность получается из BCD кода непосредственно. Дополнительный разряд р называется контрольным разрядом четности;

код “2 из 5”- это код, состоящий из всех десяти возможных комбинаций пятиразрядных кодовых наборов с двумя единицами. Этот код – взвешенный (кроме кодового набора для 0). Он может быть получен из двоичного кода 1247.

В каждом коде число единиц в любом кодовом наборе чётно. При появлении одиночной ошибки допустимый кодовый набор преобразуется в неправильный. Поэтому можно обнаружить ошибку.

Пусть необходимо построить двухразрядный код с проверкой на четность (нечетность). Из четырех возможных комбинаций можно сформировать 2 кода с проверкой на: а) четность 00, 11; б) нечетность 01, 10. В табл. 14 приведены кодовые наборы для двух-, трех- и четырехразрядных кодов.

Таблица 14

Двухразрядный код с проверкой на	Трехразрядный код с проверкой на	Четырехразрядный код с проверкой на
четность	нечетность	четность	нечетность	четность	нечетность

В общем случае для построения n-разрядного кода с обнаружением ошибок требуется не более половины из 2ⁿ возможных комбинаций из n разрядов. Выбор кодовых наборов производится таким образом, чтобы для преобразования одного кодового набора в другой допустимый кодовый набор, по крайней мере, два разряда должны иметь противоположные значения.

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

Определение. Кодовым расстоянием d между двумя кодовыми наборами называется число их несовпадающих разрядов.

Пример. Кодовое расстояние между 1100 и 0011 d = 4.

Определение. Минимальным кодовым расстоянием d_min называется наименьшее число разрядов, в которых различаются любые два кодовых набора.

Пример. Для кода 8421 минимальное кодовое расстояние d_min= 1, для кодов, приведенных в таблицах d_min= 2.

Правило. Код является кодом с обнаружением ошибок тогда и только тогда, когда его минимальное кодовое расстояние не меньше двух.

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