- •«Калининградский государственный технический университет»
- •230100.62 «Информатика и вычислительная техника» и
- •230700.62 «Прикладная информатика»
- •Оглавление
- •Введение
- •1. Основные понятия информатики и информации
- •1.1. Информатизация общества
- •1.2. Понятие информатики
- •1.3. Понятие и характерные черты информации
- •1.4. Классификация информации
- •1.5. Свойства информации
- •2. Кодирование информации
- •2.1. Виды сигнала как материального носителя информации
- •2.2. Преобразования сигнала
- •2.3. Системы счисления
- •2.4. Правила перевода чисел
- •2.4.1. Правила перевода целых чисел
- •2.4.2. Правила перевода правильных дробей
- •2.4.3. Правило перевода неправильных дробей
- •2.5. Правила выполнения простейших арифметических действий
- •2.6. Кодирование дискретного сигнала
- •2.7. Кодирование по образцу
- •2.7.1. Прямые коды
- •2.7.2.Ascii-коды
- •2.7.3. Коды, учитывающие частоту информационных элементов
- •2.7.4. Коды Грея
- •2.8. Криптографическое кодирование
- •2.8.1. Метод простой подстановки
- •2.8.2. Метод Виженера
- •2.9. Эффективное кодирование
- •2.9.1. Универсальные методы
- •2.9.1.1. Метод Шеннона-Фано
- •2.9.1.2. Метод Хаффмена
- •2.9.1.3. Повышение эффективности кодирования универсальными кодами
- •2.9.1.4. Декодирование эффективных кодов
- •2.9.2. Специальные методы эффективного кодирования
- •2.9.2.1. Методы эффективного кодирования числовых последовательностей
- •2.9.2.2. Методы эффективного кодирования словарей
- •Основной вспомогательный
- •2.9.2.3. Методы эффективного кодирования естественно-языковых текстов
- •2.10. Помехозащитное кодирование
- •2.10.1. Искажение кодовых комбинаций
- •2.10.2. Кодовое расстояние и корректирующая способность кода
- •2.10.3. Коды, исправляющие ошибки
- •3. Измерение дискретного сигнала
- •3.1. Структурный подход к измерению информации
- •3.1.1. Геометрическая мера
- •3.1.2. Комбинаторная мера
- •3.1.3. Аддитивная мера
- •3.2. Статистический подход к измерению информации
- •3.3. Семантический подход к измерению информации
- •3.3.1. Целесообразность информации
- •3.3.2. Полезность информации
- •3.3.3. Истинность информации
- •3.4. Качество информации
- •Технические средства информатики
- •4.1. Структура компьютера и принципы его функционирования
- •4.2. Виды современных компьютеров
- •4.3. Структурные элементы компьютера
- •4.3.1. Память
- •4.3.1.1. Внутренняя память
- •4.3.1.2. Внешняя память
- •4.3.2. Устройство управления
- •4.3.3. Арифметико-логическое устройство
- •4.3.3.1. Формы представления целых чисел
- •4.3.3.2. Формы представления вещественных чисел
- •4.3.3.3. Коды представления числовых данных
- •4.3.3.4. Принципы выполнения арифметической операции сложения
- •Приложение 1. Положения комбинаторики, используемые в измерении информации
3.1.3. Аддитивная мера
Эта мера предложена в 1928 году американским ученым Хартли, поэтому имеет второе название – мера Хартли. Хартли впервые ввел специальное обозначение для количества информации – I и предложил следующую логарифмическую зависимость между количеством информации и мощностью исходного алфавита:
I = l log h,
где I – количество информации, содержащейся в сообщении;
l– длина сообщения;
h – мощность исходного алфавита.
При исходном алфавите {0,1}; l= 1; h = 2 и основании логарифма, равном 2, имеем
I=1*log22=1.
Данная формула даёт аналитическое определение бита (BIT - BInary digiT) по Хартли: это количество информации, которое содержится в двоичной цифре.
Единицей измерения информации в аддитивной мере является бит.
Пример 3.3. Рассчитать количество информации, которое содержится в шестнадцатеричном и двоичном представленииASCII-кода для числа 1.
В соответствии с таблицей ASCII-кодов имеем:
шестнадцатеричное представление числа 1 – 31, I=2log216=8 бит,
двоичное представление числа 1 – 00110001, I=8log22=8 бит.
Таким образом, разные представления ASCII-кода для одного символа содержат одинаковое количество информации, измеренной аддитивной мерой.
3.2. Статистический подход к измерению информации
В 30-х годах ХХ века американский ученый Клод Шеннон предложил связать количество информации, которое несет в себе некоторое сообщение, с вероятностью получения этого сообщения.
Вероятность p – количественная априорная (т.е. известная до проведения опыта) характеристика одного из исходов (событий) некоторого опыта. Измеряется в пределах от 0 до 1. Если заранее известны все исходы опыта, сумма их вероятностей равна 1, а сами исходы составляютполную группу событий. Если все исходы могут свершиться с одинаковой долей вероятности, они называютсяравновероятными.
Например, пусть опыт состоит в сдаче студентом экзамена по информатике. Очевидно, у этого опыта всего 4 исхода (по количеству возможных оценок, которые студент может получить на экзамене). Тогда эти исходы составляют полную группу событий, т.е. сумма их вероятностей равна 1. Если студент учился хорошо в течение семестра, значения вероятностей всех исходов могут быть такими: p(5)=0,5;p(4)=0,3;p(3)=0,1;p(2)=0,1. Здесь записьp(j) означает вероятность исхода, когда получена оценкаj(j={2,3,4,5}).
Если студент учился плохо, можно заранее оценить возможные исходы сдачи экзамена, т.е. задать вероятности исходов, например, следующим образом: p(5)=0,1;p(4)=0,2;p(3)=0,4;p(2)=0,3.
В обоих случаях выполняется условие:
где n– число исходов опыта,
i– номер одного из исходов.
Пусть можно получить nсообщений по результатам некоторого опыта (т.е. у опыта естьnисходов), причем известны вероятности получения каждого сообщения (исхода) -pi. Тогда в соответствии с идеей Шеннона, количество информацииIв сообщенииiопределяется по формуле:
I=-log2 pi,
где pi– вероятностьi-го сообщения (исхода).
Пример 3.4. Определить количество информации, содержащейся в сообщении о результате сдачи экзамена для студента-хорошиста, для которогоp(5)=0,5;p(4)=0,3;p(3)=0,1;p(2)=0,1.
Пусть I(j) – количество информации в сообщении о получении оценкиj. Тогда имеем:
I(5) = -log2 0,5 = 1,
I(4) = -log2 0,3 = 1,74,
I(3) = -log2 0,1 = 3,32,
I(2) = -log20,1 = 3,32.
Пример 3.5. Определить количество информации, содержащейся в сообщении о результате сдачи экзамена для плохо успевающего студента, для которогоp(5)=0,1;p(4)=0,2;p(3)=0,4;p(2)=0,3:
I(5) = -log2 0,1 = 3,32,
I(4) = -log2 0,2 = 2,32,
I(3) = -log2 0,4 = 1,32,
I(2) = -log20,3 = 1,74.
Таким образом, количество получаемой с сообщением информации тем больше, чем неожиданнее данное сообщение.
Этот тезис использован при эффективном кодировании кодами переменной длины (т.е. имеющими разную геометрическую меру): исходные символы, имеющие большую частоту (или вероятность), имеют код меньшей длины, т.е. несут меньше информации в геометрической мере, и наоборот.
Соотношение I=-log2piпозволяет определять также размер двоичного эффективного кода, требуемого для представления того или иного сообщения, имеющего определенную вероятность появления. Поскольку размер кодовой комбинации – целое число модифицируем формулу:l=[-log2pi], гдеl– число разрядов кода, скобки [] означают округление в сторону ближайшего большего числа.
Пример 3.6. Есть 4 сообщения:a, b, c, d с вероятностями, соответственно, р(a)=0,5; р(b)=0,25; р(c)=0,125; р(d)=0,125. Определить число двоичных разрядов, требуемых для кодирования каждого их четырех сообщений:
l(a) = [-log20,5] = 1,
l(b) = [-log20,25] = 2,
l(c) = [-log20,125] = 3,
l(d) = [-log20,125] = 3.
Помимо информационной оценки одного сообщения, Шеннон предложил количественную информационную оценку всех сообщений, которые можно получить по результатам проведения некоторого опыта. Так, среднее количество информации Iср, получаемой со всемиnсообщениями, определяется по формуле:
где pi – вероятностьi-го сообщения.
Пример 3.7. Определить среднее количество информации, получаемое студентом-хорошистом, по всем результатам сдачи экзамена:
Iср = - (0,5*log20,5 + 0,3*log20,3 + 0,1*log20,1 + 0,1*log20,1) = 1,67.
Пример 3.8. Определить среднее количество информации, получаемое плохо успевающим студентом, по всем результатам сдачи экзамена:
Iср = - (0,1*log20,1 + 0,2*log20,2 + 0,4*log20,4 + 0,3*log20,3) = 1,73.
Большее количество информации, получаемое во втором случае, объясняется большей непредсказуемостью результатов: в самом деле, у отличника два исхода равновероятны.
Пусть у опыта два равновероятных исхода, составляющих полную группу событий, т.е. p1 = p2= 0,5. Тогда имеем:
Iср = -(0,5*log20,5 + 0,5*log20,5) = 1.
Эта формула есть аналитическое определение бита по Шеннону: это среднее количество информации, которое содержится в двух равновероятных исходах некоторого опыта, составляющих полную группу событий.
Единица измерения информации при статистическом подходе – бит.
На практике часто вместо вероятностей используются частоты исходов. Это возможно, если опыты проводились ранее и существует определенная статистика их исходов. Так, строго говоря, в построении эффективных кодов участвуют не частоты символов, а их вероятности.