2. Коды, обнаруживающие одиночную ошибку

Задача обнаружения ошибки может быть решена довольно легко. Достаточно просто передавать каждую букву сообщения дважды. Например, при необходимости передачи слова «гора» можно передать «ггоорраа». При получении искаженного сообщения, например, «гготрраа» с большой вероятностью (практически, достоверно) можно догадаться, каким было исходное слово. Конечно, возможно такое искажение, которое делает неоднозначным интерпретацию полученного сообщения. Однако цель такого способа кодирования состоит не в исправлении ошибки, а в обнаружении факта искажения и в повторной передаче подозрительной на наличие ошибки части сообщения. Недостаток данного способа обеспечения надежности состоит в том, что относительная избыточность сообщения оказывается очень большой – очевидно, .

Так как должен быть установлен только факт наличия ошибки, можно предложить и другой способ, позволяющий с высокой вероятностью обнаружить ошибку в сообщении. Суть этого способа заключается в следующем. На входе в канал связи производится подсчет числа единиц в двоичной кодовой последовательности – во входном сообщении. Если число единиц оказывается нечетным, то в хвост передаваемого сообщения добавляется «1», а если нет, то «0». Таким образом, к сообщению добавляют так называемый контрольный бит четности, чтобы суммарное количество единиц вместе с этим контрольным битом было четным. На принимающем конце канала связи производится аналогичный подсчет числа единиц, и если контрольная сумма единиц в принятой кодовой последовательности оказывается нечетной, то делается вывод о том, что при передаче произошло искажение информации, в противном случае принятая информация признается правильной. Разумеется, этот способ отнюдь не совершенен и применяется, когда вероятность ошибки не очень велика. При контроле на четность единственный способ получить достоверную информацию – это повторная передача сообщения.

Избыточность сообщения при контроле на четность равна:

. (14.2)

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

3. Коды, исправляющие одиночную ошибку

По аналогии с предыдущим пунктом можно было бы предложить простой способ установления факта наличия ошибки – передавать каждый символ сообщения трижды, например, «гггооорррааа» – тогда при получении, например, сообщения «гггооопррааа» ясно, что ошибочной является буква «п» и ее следует заменить на «р». Безусловно, при этом предполагается, что вероятность появления парной ошибки невелика. Такой метод кодирования приводит к огромной избыточности сообщения , что неприемлемо с экономической точки зрения.

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

, (14.3)

где p – вероятность появления ошибки в сообщении (искажения этого бита, то есть его инверсии в случае двоичного кодирования нулями и единицами). Для восстановления информационного содержания сообщения следует дополнительно передать количество информации не менее величины ее потерь, то есть вместо передачи каждого 1 бита следует передавать бит. При этом избыточность сообщения составит как миимум

. (14.4)

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

Выражение (14.4) указывает нижнюю границу избыточности, необходимой для восстановления информации. Однако поиск конкретного способа осуществления кодирования, при котором ошибка может быть локализована (то есть определено, в каком конкретно бите она находится) и устранена – отдельная задача, которую мы теперь и обсудим. Изложенный ниже метод кодирования был предложен в 1948 году Р. Хеммингом; построенные по этому методу коды получили название «коды Хемминга».

Основная идея такого кодирования состоит в добавлении к информационным битам нескольких битов четности, каждый из которых контролирует определенные информационные биты. Если пронумеровать все передаваемые биты (вместе с битами четности) слева направо (напомним, что информационные биты нумеруются справа налево – от 0 до 7), то контрольными (проверочными) оказываются биты, номера которых равны степени 2, а остальные биты являются информационными. Например, для 8-битного информационного кода «01101101» передаваемый код (код Хемминга) будет 12-битным, так как к информационному коду добавятся 4 контрольных бита – 1-й, 2-й, 4-й и 8-й (рис. 7):

1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	1	1	1	0	1	1	1	0	1
		7		6	5	4		3	2	1	0

Рис. 7. Построение кода Хемминга

Принцип выделения контролируемых битов такой: для любого номера n проверочного (контрольного) бита, начиная с него, n битов подряд оказываются проверяемыми (контролируемыми), затем – группа из n непроверяемых бит, и так далее – происходит чередование групп. В число контролируемых (проверяемых) битов входит и сам контрольный (проверочный).

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

Таким образом, контрольный (проверочный) бит может содержать как нуль, так и единицу.

Номера контролируемых (прверяемых) битов для каждого контрольного приведены в табл. 22:

Табл. 22. Контрольные и контролируемые биты

Контрольные (проверочные) биты	Контролируемые (проверяемые) биты
1	1	3	5	7	9	11	13	15	17	19	21	…
2	2	3	6	7	10	11	14	15	18	19	22	…
4	4	5	6	7	12	13	14	15	20	21	22	…
8	8	9	10	11	12	13	14	15	24	25	26	…
16	16	17	18	19	20	21	22	23	24	25	26	…
32	32	33	34	35	36	37	38	39	40	41	42	…

Контрольный бит (бит четности) признается неверным, если сумма единиц в контролируемых им битах (включая его самого) нечетна.

Если контрольный бит оказался неверным, значит, в каком-то из контролируемых им битов имеется ошибка.

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

На основании сказанного можно сформулировать простой алгоритм проверки и исправления передаваемой кодовой последовательности в представлении Хемминга:

1. Произвести проверку всех битов четности;

2. Если все биты четности верны, то перейти к пункту е);

3. Вычислить сумму номеров всех неверных битов четности;

4. Инвертировать (единицу заменить на нуль или наоборот) содержимое бита, номер которого равен сумме, найденной в пункте с);

5. Исключить биты четности.

Избыточность кодов Хемминга для различных длин передаваемых кодовых последовательностей приведена в табл. 23:

Табл. 23. Избыточность кодов Хемминга для передаваемых кодовых последовательностей различной длины

Число информационных битов,	Число контрольных битов,	Избыточность, L
8	4	1.50
16	5	1.31
32	6	1.06

Количество контрольных битов определяется следующим образом (см. таблицу выше):

. (14.5)

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

Данный способ кодирования требует увеличения объема памяти компьютера приблизительно на одну треть при 16-битной длине машинного слова (см. таблицу), однако такой способ позволяет автоматически исправлять одиночные ошибки. Поэтому, оценивая время наработки на отказ этого способа, следует исходить из вероятности появления парной ошибки внутри одной кодовой последовательности (то есть сбои должны произойти в двух битах одновременно). Расчеты показывают, что для указанного ранее количества () двоичных ячеек в памяти объемом 1 Мбайт среднее время до появления сбоя при таком способе кодирования (код Хемминга) составляет более 80 лет, что, безусловно, можно считать вполне приемлемым с практической точки зрения.