Урок 9
§6. Кодирование с обнаружением ошибок
Содержание урока
Введение
Коды с исправлением ошибок
Выводы. Интеллект-карта
Вопросы и задания
Введение
Ключевые слова:
• коды с обнаружением ошибок
• избыточность
• бит чётности
• контрольная сумма
• помехоустойчивые коды
В реальных каналах связи всегда присутствуют помехи, искажающие полезный сигнал. В некоторых случаях ошибки допустимы, например при прослушивании радиопередачи через Интернет небольшое искажение звука не мешает понимать речь. Однако чаще всего требуется обеспечить точную передачу данных. Например, ошибка в передаче одной команды компьютерной программы может привести к катастрофе космического корабля. В таких случаях в первую очередь нужно обнаружить ошибку и, если это произошло, передать блок данных ещё раз. Как мы увидим, в некоторых случаях даже удаётся исправить небольшое число ошибок без повторной передачи данных.
Представьте себе, что получена цепочка нулей и единиц 1010101110, причём биты независимы: каждый бит цепочки может быть нулём или единицей независимо от других. В этом случае нет абсолютно никакой возможности определить, верно ли передана последовательность. Поэтому для того, чтобы обнаружить ошибку, в передаваемое сообщение нужно добавлять какую-то дополнительную информацию («лишние» биты), т. е. вводить избыточность.
Простейший вариант — добавить в конец блока данных дополнительный бит, который будет равен 1, если в основном сообщении нечётное число единиц, и равен 0 для сообщения с чётным числом единиц. В результате в новом блоке всегда будет чётное число единиц. Этот дополнительный бит называется битом чётности. Бит чётности используется при передаче данных в компьютерных сетях.
К каждому из этих двухбитных сообщений добавьте бит чётности (так, чтобы общее число единичных битов в каждом сообщении стало чётным):
00 01 10 11
Сообщения передаются с битом чётности. Какие из этих сообщений были переданы с ошибкой?
00101 0011010101 1001001010011
Как вы рассуждали?
Как вы думаете, можно ли вместо бита чётности добавлять «бит нечётности», который делает общее число единичных битов в блоке данных нечётным?
К каждому из этих сообщений добавьте бит чётности;
1000 0110 1011101011 11111111
При передаче сообщения с битом чётности произошли две ошибки. Сможет ли обнаружить ошибку принимающая сторона? А если ошибок будет три? Четыре?
Получено сообщение с битом чётности, в котором оказалось нечётное число единиц. Можно ли сказать, в каком именно бите произошла ошибка?
Если при передаче изменились два бита, чётность не меняется, и такая ошибка не обнаруживается. Однако на практике две ошибки в одном небольшом (например, 8-битном) блоке данных могут появиться очень редко.
Применение бита чётности позволяет обнаруживать нечётное число ошибок (1, 3, 5, ...), а ошибки в чётном количестве разрядов остаются незамеченными.
При передаче больших файлов может сразу возникнуть множество ошибок, поэтому используют другой метод — вычисляют контрольную сумму файла (по достаточно сложным алгоритмам), которая передаётся вместе с данными. Изменение даже одного бита данных сильно изменяет контрольную сумму. Если контрольная сумма файла, вычисленная приёмником, не совпадает с контрольной суммой, записанной передающей стороной, то произошла ошибка.
Следующая страница 
Коды с исправлением ошибок
Cкачать материалы урока
