- •Предисловие
- •Лекция 1. Информация. Начальные понятия и определения
- •1. Информация и данные
- •2. Адекватность и формы адекватности информации
- •3. Качество информации
- •4. Понятие об информационном процессе
- •5. Формы представления информации
- •6. Преобразование сообщений
- •Лекция 2. Необходимые сведения из теории вероятностей
- •1. Понятие вероятности
- •2. Сложение вероятностей независимых несовместных событий
- •3. Умножение вероятностей независимых совместных событий
- •4. Нахождение среднего для значений случайных независимых величин
- •5. Понятие условной вероятности
- •6. Общая формула для вероятности произведения событий
- •7. Общая формула для вероятности суммы событий
- •Лекция 3. Понятие энтропии
- •1. Энтропия как мера неопределенности
- •2. Свойства энтропии
- •3. Условная энтропия
- •Лекция 4. Энтропия и информация
- •1. Объемный подход к измерению количества информации
- •2. Энтропийный подход к измерению количества информации
- •Лекция 5. Информация и алфавит
- •Лекция 6. Постановка задачи кодирования. Первая теорема Шеннона.
- •Лекция 7. Способы построения двоичных кодов. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды.
- •1. Постановка задачи оптимизации неравномерного кодирования
- •00100010000111010101110000110
- •2. Неравномерный код с разделителем
- •3. Коды без разделителя. Условие Фано
- •00100010000111010101110000110
- •00100010000111010101110000110
- •4. Префиксный код Шеннона–Фано
- •5. Префиксный код Хаффмана
- •Лекция 8. Способы построения двоичных кодов. Другие варианты
- •1. Равномерное алфавитное двоичное кодирование. Байтовый код
- •2. Международные системы байтового кодирования текстовых данных. Универсальная система кодирования текстовых данных
- •3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе
- •4. Блочное двоичное кодирование
- •101010111001100010000000001000000000000001
- •5. Кодирование графических данных
- •6. Кодирование звуковой информации
- •Лекция 9. Системы счисления. Представление чисел в различных системах счисления. Часть 1
- •1. Системы счисления
- •2. Десятичная система счисления
- •3. Двоичная система счисления
- •4. 8- И 16-ричная системы счисления
- •5. Смешанные системы счисления
- •6. Понятие экономичности системы счисления
- •Лекция 10. Системы счисления. Представление чисел в различных системах счисления. Часть 2.
- •1. Задача перевода числа из одной системы счисления в другую
- •2. Перевод q p целых чисел
- •3. Перевод p q целых чисел
- •4. Перевод p q дробных чисел
- •6. Перевод чисел между 2-ичной, 8-ричной и 16-ричной системами счисления
- •Лекция 11. Кодирование чисел в компьютере и действия над ними
- •1. Нормализованные числа
- •2. Преобразование числа из естественной формы в нормализованную
- •3. Преобразование нормализованных чисел
- •4. Кодирование и обработка целых чисел без знака
- •5. Кодирование и обработка целых чисел со знаком
- •6. Кодирование и обработка вещественных чисел
- •Лекция 12. Передача информации в линии связи
- •1. Общая схема передачи информации в линии связи
- •2. Характеристики канала связи
- •3. Влияние шумов на пропускную способность канала
- •Лекция 13. Обеспечение надежности передачи информации.
- •1. Постановка задачи обеспечения надежности передачи
- •2. Коды, обнаруживающие одиночную ошибку
- •3. Коды, исправляющие одиночную ошибку
- •Лекция 14. Способы передачи информации в компьютерных линиях связи
- •1. Параллельная передача данных
- •2. Последовательная передача данных
- •3. Связь компьютеров по телефонным линиям
- •Лекция 15. Классификация данных. Представление данных в памяти компьютера
- •1. Классификация данных
- •2. Представление элементарных данных в озу
- •Лекция 16. Классификация структур данных
- •1. Классификация и примеры структур данных
- •2. Понятие логической записи
- •Лекция 17. Организация структур данных в оперативной памяти и на внешних носителях
- •1. Организация структур данных в озу
- •2. Иерархия структур данных на внешних носителях
- •3. Особенности устройств хранения информации
- •Контрольные вопросы
- •Список литературы
Лекция 13. Обеспечение надежности передачи информации.
Постановка задачи обеспечения надежности передачи
Коды, обнаруживающие одиночную ошибку
Коды, исправляющие одиночную ошибку
1. Постановка задачи обеспечения надежности передачи
Все реальные каналы связи подвержены воздействию помех. Означает ли это, что надежная (то есть без потерь) передача по ним информации невозможна в принципе? К. Шеннон доказал теоретическую возможность передачи сообщения без потерь информации по реальным каналам, если обеспечить выполнение ряда условий. Задача была сформулирована в виде теоремы, которая затем получила строгое математическое доказательство. Ранее была представлена первая теорема Шеннона, касающаяся кодирования информации при передаче по идеальному каналу связи. Критерием оптимальности кодирования служила избыточность кода. Эту избыточность можно сделать сколь угодно малой (близкой к нулю), применяя блочное кодирование по методу Хаффмана.
Вторая теорема Шеннона касается реальных каналов связи и гласит:
При передаче информации по каналу с шумом всегда существует способ кодирования, при котором сообщение будет передаваться со сколь угодно высокой достоверностью, если скорость передачи не превышает пропускной способности канала.
Последняя часть определения, относится и к идеальному каналу – в любом случае, если скорость передачи превышает пропускную способность канала, происходит потеря информации. Смысл данной теоремы в том, что при передаче по реальным каналам можно закодировать сообщение таким образом, что действие шумов не приведет к потере информации. Это достигается за счет повышения избыточности кода, то есть за счет увеличения длины кодовой цепочки. Безусловно, при этом возрастает время передачи, что следует считать платой за надежность. При этом в теореме и в ее доказательстве не указывается, каким образом следует осуществлять такое кодирование. Вторая теорема Шеннона лишь утверждает, что существует принципиальная возможность такого кодирования, причем поиск необходимого кода – это отдельная задача.
Для примера оценим, какова вероятность возникновения ошибки, но не при передаче, а при хранении информации (что не меняет сути дела). Тем самым подчеркнем важность учета влияния помех не только на передачу, но и на хранение информации. Рассмотрим следующую ситуацию. Пластмассовые корпуса микросхем памяти в компьютерах содержат в малых количествах примеси, претерпевающие -распад. Попадая в полупроводниковые элементы памяти,-частицы могут вызвать изменение их состояний, то есть искажение хранимой информации. Как часто можно ожидать такого сбоя? Лабораторные эксперименты показали, что «время наработки на отказ» отдельно взятого элемента памяти превышает миллион лет. Казалось бы, это обстятельство не дает оснований для беспокойства. Однако следует учесть, что общее количество подобных элементов в памяти компьютера весьма велико. Например, память емкостью 1 Мбайт содержит приблизительнодвоичных элементов (это соответствует количеству бит в 1 мегабайте). Следовательно, время появления ошибки в таком объеме памяти составит приблизительно
.
Предположив, что оперативная память персонального компьютера составляет 48 Мбайт, можно заключить, что время появления ошибки составляет уже около 1 дня. Нужно отметить, что в настоящее время нет экономичных технических способов исключения влияния этих ионизирующих излучений на элементы памяти. Поэтому проблема защиты информации от искажений не только при передаче, но и при хранении весьма актуальна.
Решение проблемы, как уже было сказано, состоит в использовании таких методов кодирования информации, которые позволили бы контролировать правильность передачи (или хранения) информации, а при обнаружении ошибки эти методы должны позволять исправлять ее.
Общим условием осуществимости обнаружения и исправления ошибки является использование только равномерных кодов. Во-первых, в этом случае недополучение одного из битов будет сразу свидетельствовать об ошибочности передачи, то есть постоянство длины кодовой цепочки является дополнительным средством контроля правильности передачи. Во-вторых, часто для увеличения скорости передачи используется параллельная (одновременная) передача нескольких (фиксированного, постоянного количества) бит по шинам (с фиксированной, разумеется, шириной).
Надежность передачи обеспечивается тем, что наряду с битами, непосредственно кодирующими сообщение (информационными битами), передаются (или хранятся) дополнительные биты (контрольные биты). При равномерном кодировании сообщения длина кодовой цепочки на знак (или группу знаков) первичного алфавита складывается из длины информационной частии числа контрольных битов. Определим избыточностьL сообщения для реального канала связи:
. (14.1)
Избыточность сообщения– это величина, показывающая, во сколько раз требуется удлинить сообщение, чтобы обеспечить его надежную (безошибочную) передачу (хранение).
Таким образом, величина L характеризует эффективность кодирования при передаче по реальным каналам. Если какие-то два способа кодирования обеспечивают одинаковую надежность передачи, то при равных надежностях предпочтение должно быть отдано тому способу, при котором избыточность окажется наименьшей. Однако надо отметить, что для практики важна еще и простота того или иного способа кодирования.
Далее рассмотрим отдельно две ситуации:
способ кодирования обеспечивает только установление факта искажения информации – в этом случае исправление ошибки производится путем повторной передачи сообщения;
способ кодирования позволяет локализовать (обнаружить факт существования ошибки и найти ее) и автоматически исправить ошибку передачи (хранения).