Лекция 13. Обеспечение надежности передачи информации.

1. Постановка задачи обеспечения надежности передачи

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

3. Коды, исправляющие одиночную ошибку

1. Постановка задачи обеспечения надежности передачи

Все реальные каналы связи подвержены воздействию помех. Означает ли это, что надежная (то есть без потерь) передача по ним информации невозможна в принципе? К. Шеннон доказал теоретическую возможность передачи сообщения без потерь информации по реальным каналам, если обеспечить выполнение ряда условий. Задача была сформулирована в виде теоремы, которая затем получила строгое математическое доказательство. Ранее была представлена первая теорема Шеннона, касающаяся кодирования информации при передаче по идеальному каналу связи. Критерием оптимальности кодирования служила избыточность кода. Эту избыточность можно сделать сколь угодно малой (близкой к нулю), применяя блочное кодирование по методу Хаффмана.

Вторая теорема Шеннона касается реальных каналов связи и гласит:

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

Последняя часть определения, относится и к идеальному каналу – в любом случае, если скорость передачи превышает пропускную способность канала, происходит потеря информации. Смысл данной теоремы в том, что при передаче по реальным каналам можно закодировать сообщение таким образом, что действие шумов не приведет к потере информации. Это достигается за счет повышения избыточности кода, то есть за счет увеличения длины кодовой цепочки. Безусловно, при этом возрастает время передачи, что следует считать платой за надежность. При этом в теореме и в ее доказательстве не указывается, каким образом следует осуществлять такое кодирование. Вторая теорема Шеннона лишь утверждает, что существует принципиальная возможность такого кодирования, причем поиск необходимого кода – это отдельная задача.

Для примера оценим, какова вероятность возникновения ошибки, но не при передаче, а при хранении информации (что не меняет сути дела). Тем самым подчеркнем важность учета влияния помех не только на передачу, но и на хранение информации. Рассмотрим следующую ситуацию. Пластмассовые корпуса микросхем памяти в компьютерах содержат в малых количествах примеси, претерпевающие -распад. Попадая в полупроводниковые элементы памяти,-частицы могут вызвать изменение их состояний, то есть искажение хранимой информации. Как часто можно ожидать такого сбоя? Лабораторные эксперименты показали, что «время наработки на отказ» отдельно взятого элемента памяти превышает миллион лет. Казалось бы, это обстятельство не дает оснований для беспокойства. Однако следует учесть, что общее количество подобных элементов в памяти компьютера весьма велико. Например, память емкостью 1 Мбайт содержит приблизительнодвоичных элементов (это соответствует количеству бит в 1 мегабайте). Следовательно, время появления ошибки в таком объеме памяти составит приблизительно

.

Предположив, что оперативная память персонального компьютера составляет 48 Мбайт, можно заключить, что время появления ошибки составляет уже около 1 дня. Нужно отметить, что в настоящее время нет экономичных технических способов исключения влияния этих ионизирующих излучений на элементы памяти. Поэтому проблема защиты информации от искажений не только при передаче, но и при хранении весьма актуальна.

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

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

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

. (14.1)

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

Таким образом, величина L характеризует эффективность кодирования при передаче по реальным каналам. Если какие-то два способа кодирования обеспечивают одинаковую надежность передачи, то при равных надежностях предпочтение должно быть отдано тому способу, при котором избыточность окажется наименьшей. Однако надо отметить, что для практики важна еще и простота того или иного способа кодирования.

Далее рассмотрим отдельно две ситуации:

• способ кодирования обеспечивает только установление факта искажения информации – в этом случае исправление ошибки производится путем повторной передачи сообщения;

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