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

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

Поскольку ошибка должна быть только обнаружена, можно предложить другой способ кодирования. Пусть имеется цепочка информационных бит длиной k_i. Добавим к ним один контрольный бит (k_c = 1), значение которого определяется тем, что новая кодовая цепочка из k_i + 1 бит должна содержать четное количество единиц - по этой причине такой контрольный бит называется битом четности. Например, для информационного байта 01010100 бит четности будет иметь значение 1, а для байта 11011011 бит четности равен 0. В случае одиночной ошибки передачи число 1 перестает быть четным, что и служит свидетельством сбоя. Например, если получена цепочка 110110111 (контрольный бит выделен подчеркиванием), ясно, что передача произведена с ошибкой, поскольку общее количество единиц равно 7, т.е. нечетно. Предложенный способ кодирования не позволяет установить, в каком конкретно бите содержится ошибка и, следовательно, не дает возможности ее исправить. Избыточность сообщения при этом равна:

На первый взгляд кажется, что путем увеличения k_i можно сколь угодно приближать избыточность к ее минимальному значению (L_min = 1). Однако с ростом k_i, во-первых, растет вероятность парной ошибки, которая контрольным битом не отслеживается; во-вторых, при обнаружении ошибки потребуется заново передавать много информации. Поэтому обычно k_i = 8 или 16 и, следовательно, L = 1,125 (1,0625).