Обеспечение надежности передачи и хранения информации

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

Из этой теоремы следуют два вывода:

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

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

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

При этом возможны два варианта построения таких кодов:

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

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

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

Надежность передачи обеспечивается тем, что наряду с битами, непосредственно кодирующими сообщение (информационными битами), передаются (хранятся) дополнительные биты (контрольные биты), по состоянию которых можно судить о правильности передачи.

При равномерном кодировании сообщения длина кодовой цепочки на знак (или группу знаков) k складывается из длины информационной части k0 и числа контрольных битов kc (очевидно, k ³ k0).

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

Для оценки выбранного способа кодирования используют величину, которая называется относительной избыточностью кода (L):

Относительная избыточность – это характеристика, показывающая, во сколько раз требуется удлинить сообщение, чтобы обеспечить его надежную (безошибочную) передачу (хранение).

Безусловно, при равных надежностях передачи предпочтение должно быть отдано тому способу кодирования, при котором L будет наименьшим.

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

Контроль по четности

Пусть имеется цепочка информационных бит длиной k₀. Добавим к ним контрольный бит k_с, значение которого определяется тем, что новая кодовая цепочка из k₀+1 бита должна содержать четное количество единиц – по этой причине такой контрольный бит называется битом четности.

Например,

- для информационного кода 01010100 бит четности будет иметь значение 1,

- для кода 11011011 бит четности равен 0.

В случае одиночной ошибки передачи число 1 перестает быть четным, что и служит свидетельством сбоя.

Например, в случае получения сообщения 101101111 становится понятным, что передача произведена с ошибкой, поскольку общее количество единиц равно 7, т.е. нечетно.

В каком бите содержится ошибка при таком способе кодирования установить нельзя. Избыточность кода в данном случае, очевидно, равна: =1+1/8=1,125.

На первый взгляд кажется, что путем увеличения k₀ можно сколь угодно приближать избыточность к ее минимальному значению (L_min = 1).

Однако с ростом k_0:

- растет вероятность парной ошибки, которая контрольным битом не отслеживается;

- при обнаружении ошибки потребуется заново передавать много информации.

Поэтому обычно k₀ = 8 или 16 и, следовательно, L=1,125 (1,0625).

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

Контроль по нечетности

Этот способ идентичен предыдущему, но значение контрольного бита k_с, значение которого определяется тем, что новая кодовая цепочка из k₀+1 бита должна содержать нечетное количество единиц.