- •Предисловие
- •Лекция 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. Особенности устройств хранения информации
- •Контрольные вопросы
- •Список литературы
Лекция 8. Способы построения двоичных кодов. Другие варианты
Равномерное алфавитное двоичное кодирование. Байтовый код
Международные системы байтового кодирования текстовых данных. Универсальная система кодирования текстовых данных
Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе
Блочное двоичное кодирование
Кодирование графических данных
Кодирование звуковой информации
1. Равномерное алфавитное двоичное кодирование. Байтовый код
В случае равномерногоалфавитного кодирования двоичный код первичного алфавита строится цепочкамиравной длины, то есть со всеми знаками первичного алфавитаAсвязано одинаковое количество информации, равное. Формировать признак конца строки не требуется, приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку первичного алфавита она соответствует), соотнося ее с таблицей кодов. Длину кода (соответствующего одному символу первичного алфавита)задают, исходя из известной формулы.
При идентификации кодовой цепочки недопустимы сбои. Например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации. Эта проблема решается путем синхронизации передачи данных или иными способами.
С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи данных. Дело в том, что факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.
Примеромравномерного алфавитного кодирования является телеграфныйкод Бодо, пришедший на смену азбуке Морзе.
Код Бодо применим для кодирования сообщений, первичный алфавит которых содержит не более 32-х символов. Тогда , и выбирают, то есть каждый знак первичного алфавита содержит 5 бит информации и кодируется цепочкой из 5 двоичных знаков.
В русском алфавите 34 буквы (с пробелом), именно по этой причине пришлось «сжать» алфавит и объединить в один знак «е» и «ё», а также «ь» и «ъ». После такого сжатия как раз , однако, не остается свободных кодов для знаков препинания, поэтому в телеграммах знаки препинания отсутствуют или заменяются буквенными аббревиатурами. Это не является существенным ограничением, поскольку, как указывалось выше, избыточность языка позволяет легко восстановить информационное cодержание сообщения.
Условие , очевидно, выполняется для языков, основанных на латинском алфавите ().
Избыточность кода Бодо для русского языка , для английского –.
Другим важнымдля наспримеромиспользования равномерного алфавитного кодирования являетсяпредставлениесимвольной (знаковой)информации в компьютере.
Чтобы задать (определить) необходимую длину кода (для каждого символа первичного алфавита), необходимо начать с установления количества знаков в этом самом первичном алфавите. Компьютерный алфавит должен включать в себя:
26 2 = 52 букв латинского алфавита (с учетом заглавных и маленьких букв);
33 2 = 66 букв русского алфавита (с учетом заглавных и маленьких букв);
цифры 0…9 – всего 10 цифр;
знаки препинания, знаки математических операций, спецсимволы – всего приблизительно 20 штук.
Таким образом, получаем, что общее число символов в первичном компьютерном алфавите штук.
Теперь можно оценить длину кодовой цепочки, представляющей каждый символ первичного компьютерного алфавита:
. Таким образом,.
Поскольку длина кода выражается целым числом, очевидно, необходимо и достаточно принять .
Именно такой способ кодирования принят в компьютерных системах: любому символу ставится в соответствие код из 8 двоичных разрядов (8 бит). Эта последовательность сохраняется и обрабатывается как единое целое, то есть отсутствует доступ к отдельному биту, а имеется доступ к этой последовательности 8 битов как к целому. По этой причине разрядность устройств компьютера, предназначенных для хранения или обработки информации, кратна 8.
Совокупность восьми связанных битов получила название байт.
Представление символов байтами называется байтовым кодированием.
Байт наряду с битом может использоваться как единица измерения количества информации в сообщении. Один байт соответствует количеству информации в одном знаке алфавита в предположении их равновероятного распределения. Этот сопособ измерения количества информации называетсяобъемным. 1 байт принят в качестве единицы измерения количества информации в международной системе единиц СИ.
Наряду с байтом для измерения количества информации используются более крупные производные единицы – килобайт, мегабайт, гигабайт, терабайт:
1 Кбайт = 210байт = 1024 байт;
1 Мбайт = 220байт = 1024 Кбайт;
1 Гбайт = 230байт = 1024 Мбайт;
1 Тбайт = 240байт = 1024 Гбайт.
Использование 8-битных цепочек позволяет закодировать символов, что превышает оцененное выше значениечисла компьютерных символов. Следовательно, использование байтового кодирования символов первичного (здесь – компьютерного) алфавита дает возможность употребить оставшуюся часть (возможных символов) для представления дополнительных символов.
Пусть имеется некоторое сообщение (последовательность знаков). Оценка количества информации на знак первичного алфавита согласно вероятностному подходу (с помощью формулы Шеннона) дает , а объемная мера равна. Соотношение между этими величинами таково:
.
Это соотношение следует из формулы
.