"Информатика", Поляков К.Ю., Еремин Е.А.
При передаче или хранении двоичные данные могут измениться из-за помех и сбоев. Чтобы обнаружить ошибку, к сообщению добавляют избыточную информацию: контрольные разряды, суммы или повторения. Получается код с обнаружением ошибок: получатель проверяет контрольные данные и узнаёт, нарушено ли сообщение. Главное правило проверки чётности — общее число единиц должно соответствовать заранее выбранному условию.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Избыточное кодирование — добавление к исходным данным дополнительных символов для контроля правильности передачи. Эти символы не обязательно содержат новые сведения о сообщении. Они создают возможность проверить, не изменились ли данные по дороге.
Код с обнаружением ошибок — код, по которому можно установить, что переданное сообщение изменилось. Получатель сравнивает принятую комбинацию с правилами допустимого кода. Такой код сообщает о нарушении, но не всегда показывает место ошибки.
Контрольный разряд — дополнительный бит, значение которого вычисляется по исходным битам. Его часто записывают в конце двоичной последовательности. По нему проверяют, соответствует ли принятое кодовое слово установленному правилу.
Проверка чётности — способ контроля, при котором общее число единиц должно быть чётным или нечётным. Вид проверки выбирают заранее, а затем одинаково применяют при отправке и приёмe. Например, при чётной проверке в правильном слове должно быть 0, 2, 4 и так далее единицы.
Ошибки возникают из-за помех в канале связи, неисправностей оборудования или сбоев при записи данных. Отдельный бит может изменить значение с 0 на 1 или с 1 на 0. Обычный двоичный код не отличает правильное сообщение от изменённого, потому что после замены получается другая, но внешне такая же последовательность битов.
Избыточность добавляет к данным правило, которому должны соответствовать допустимые кодовые комбинации. Например, при чётной проверке слово с пятью единицами недопустимо, а слово с четырьмя единицами допустимо. Если из-за ошибки принято недопустимое слово, получатель понимает, что передача нарушена.
При формировании контрольного разряда сначала считают единицы только в исходных данных. При чётной проверке ставят 0, если их количество уже чётное, и 1, если оно нечётное. При нечётной проверке поступают наоборот: контрольный бит выбирают так, чтобы итоговое число единиц стало нечётным.
Изменение одного бита меняет число единиц на один: оно либо увеличивается, либо уменьшается. Поэтому чётность результата обязательно меняется, и проверка обнаруживает такую ошибку. Если изменились два бита, возможны одновременные замены 0 на 1 и 1 на 0, тогда число единиц не изменится, а ошибка останется незаметной.
Отправитель сначала добавляет контрольные данные к сообщению и передаёт полученное кодовое слово. Получатель отделяет исходные данные, повторяет вычисление по принятой последовательности и сравнивает результат с принятой контрольной информацией. Несовпадение означает обнаруженную ошибку, но для её исправления требуется дополнительный способ определения ошибочного разряда.
| Способ | Как формируется контрольная информация | Какие ошибки обнаруживает | Ограничения |
|---|---|---|---|
| Повторение символов или блоков | Один символ или блок передают несколько раз и сравнивают копии | Ошибки, из-за которых копии стали различаться | Увеличивает объём передачи; одинаковая ошибка во всех копиях может остаться незамеченной |
| Контрольный разряд чётности | Добавляют бит, делающий общее число единиц чётным или нечётным | Любое изменение нечётного числа битов, в частности одного | Изменение чётного числа битов может не обнаружиться |
| Контрольная сумма | По группе данных вычисляют число или битовую сумму и передают её вместе с сообщением | Многие ошибки, изменяющие вычисленную сумму | Некоторые разные ошибки дают одинаковую сумму |
| Сравнение контрольной информации с принятой | Получатель заново вычисляет контрольное значение и сопоставляет его с полученным | Ошибки, при которых вычисленные значения не совпали | Само сравнение не указывает ошибочный разряд и не исправляет данные |
В таблице нужно сначала найти способ, затем посмотреть, какую информацию добавляют к сообщению. После этого сравнивают обнаруживаемые ошибки с ограничениями метода. Чем надёжнее контроль, тем больше дополнительных данных или вычислений обычно требуется.
Для последовательности 1011001 нужно определить контрольный разряд при чётной проверке и записать кодовое слово. Будем добавлять контрольный бит справа. Сначала выясним, сколько единиц уже есть в исходной последовательности.
Ответ: контрольный разряд равен 0, кодовое слово — 10110010.
Нужно проверить кодовое слово 11010101 при чётной проверке. В этом слове контрольный разряд уже включён, поэтому считаем единицы во всей последовательности. Если итоговое число чётное, слово прошло проверку.
Ответ: ошибка обнаружена, потому что в принятом кодовом слове нечётное число единиц.
Сообщение передали с контрольными разрядами по строкам и столбцам. Требуется определить ошибочный разряд по результатам проверок. Такой способ использует избыточность сразу в двух направлениях, поэтому помогает найти не только факт ошибки, но и её положение.
Ответ: ошибочный разряд находится на пересечении строки и столбца, для которых проверки чётности дали ошибку. В отличие от одной проверки всего слова, этот способ может указать положение бита.
Считать контрольный разряд частью исходного сообщения. Его значение вычисляют по исходным битам, а уже затем включают в кодовое слово. Чтобы проверить себя, сначала отделите данные от добавленного бита и только потом выполняйте расчёт.
При чётной проверке сразу выбирать бит 1. Наличие единиц ещё не означает, что контрольный бит должен быть единицей: нужно посчитать их общее количество. Если единиц чётное число, добавляют 0, если нечётное — 1.
Считать обнаружение исправлением. Нарушение проверки только сообщает, что кодовое слово подозрительно. Исправить данные можно лишь при наличии дополнительных сведений о положении ошибки.
Утверждать, что чётность обнаруживает любые ошибки. Она надёжно выявляет изменение нечётного числа битов, но два изменения могут сохранить прежнюю чётность. Проверяйте не только наличие контроля, но и его ограничения.
До изучения темы нужны знания о двоичной системе счисления и двоичном кодировании. Также пригодятся умение считать единицы и выполнять простейшие операции над битами. Эти действия позволяют самостоятельно вычислять контрольный разряд.
Дальше идея избыточности встречается при передаче данных по сетям и хранении информации. В более сложных кодах дополнительные разряды не только обнаруживают, но и помогают исправлять ошибки. Поэтому проверка чётности служит простым введением в теорию помехоустойчивого кодирования.
Зачем добавлять контрольный разряд, если он не содержит новых данных?
Он действительно не добавляет смысла сообщению, но помогает проверить его целостность. По контрольному разряду получатель может заметить, что один или несколько битов изменились.
Как понять, каким должен быть контрольный бит?
Сначала считают число единиц в исходных данных. При чётной проверке контрольный бит выбирают так, чтобы общее число единиц стало чётным, а при нечётной — чтобы оно стало нечётным.
Почему контроль чётности иногда не обнаруживает ошибку?
Изменение одного бита меняет чётность числа единиц. Но при изменении двух битов чётность может снова стать такой же, поэтому ошибка останется незамеченной.
Можно ли по контрольному разряду исправить ошибочный бит?
Обычно нельзя: проверка чётности показывает наличие ошибки, но не указывает её положение. Для исправления нужны специальные коды или дополнительные проверки, например по строкам и столбцам.
Чем код с обнаружением ошибок отличается от обычного двоичного кода?
Обычный код содержит только данные и не имеет встроенной проверки. В коде с обнаружением ошибок есть избыточные разряды, по которым можно установить факт изменения сообщения.
§ 6. Кодирование с обнаружением ошибок
