§ 6. Кодирование с обнаружением ошибок | Введение

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, углубленный уровень)


Урок 9
§6. Кодирование с обнаружением ошибок



Содержание урока

Введение

Коды с исправлением ошибок

Выводы. Интеллект-карта

Вопросы и задания


Введение


Ключевые слова:


• коды с обнаружением ошибок
• избыточность
• бит чётности
• контрольная сумма
• помехоустойчивые коды


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

Представьте себе, что получена цепочка нулей и единиц 1010101110, причём биты независимы: каждый бит цепочки может быть нулём или единицей независимо от других. В этом случае нет абсолютно никакой возможности определить, верно ли передана последовательность. Поэтому для того, чтобы обнаружить ошибку, в передаваемое сообщение нужно добавлять какую-то дополнительную информацию («лишние» биты), т. е. вводить избыточность.

Простейший вариант — добавить в конец блока данных дополнительный бит, который будет равен 1, если в основном сообщении нечётное число единиц, и равен 0 для сообщения с чётным числом единиц. В результате в новом блоке всегда будет чётное число единиц. Этот дополнительный бит называется битом чётности. Бит чётности используется при передаче данных в компьютерных сетях.

К каждому из этих двухбитных сообщений добавьте бит чётности (так, чтобы общее число единичных битов в каждом сообщении стало чётным):

00      01      10      11

Сообщения передаются с битом чётности. Какие из этих сообщений были переданы с ошибкой?

00101      0011010101      1001001010011

Как вы рассуждали?

Как вы думаете, можно ли вместо бита чётности добавлять «бит нечётности», который делает общее число единичных битов в блоке данных нечётным?

К каждому из этих сообщений добавьте бит чётности;

1000      0110      1011101011      11111111

При передаче сообщения с битом чётности произошли две ошибки. Сможет ли обнаружить ошибку принимающая сторона? А если ошибок будет три? Четыре?

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

Если при передаче изменились два бита, чётность не меняется, и такая ошибка не обнаруживается. Однако на практике две ошибки в одном небольшом (например, 8-битном) блоке данных могут появиться очень редко.

Применение бита чётности позволяет обнаруживать нечётное число ошибок (1, 3, 5, ...), а ошибки в чётном количестве разрядов остаются незамеченными.

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

Следующая страница Коды с исправлением ошибок



Cкачать материалы урока







Наверх