Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание icon

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание




НазваКонспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание
Сторінка1/10
Дата15.05.2013
Розмір0.94 Mb.
ТипКонспект лекций
  1   2   3   4   5   6   7   8   9   10


СУМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ


ТЕОРИЯ ИНФОРМАЦИИ”


Конспект лекций


для студентов заочной формы обучения


направления 080201 (Информатика)


Сумы, 2007

Содержание

С.

ПРЕДИСЛОВИЕ 3

1.1 Предмет курса. Виды информации. Теорема дискретизации 4

1.2 Базовые понятия теории информации 6

1.3 Способы измерения информации 7

1.4 Энтропия источника. Свойства количества информации и энтропии 9

^ КОНТРОЛЬНЫЕ ВОПРОСЫ 12

ТЕМА 2 ОСНОВЫ ЭКОНОМНОГО КОДИРОВАНИЯ ИНФОРМАЦИИ 13

2.1 Способы задания кодов. Статистическое кодирование 13

2.2 Оптимальные методы статистического сжатия информации 18

2.2.1 Элементы теории префиксных множеств 18

2.2.2 Статистические алгоритмы сжатия Шеннона-Фано и Хаффмена 19

2.2.3 Теоретические пределы сжатия информации 23

2.2.4 Метод блокирования сообщения. Блочный код Хаффмена 25

2.3 Арифметическое кодирование 28

^ КОНТРОЛЬНЫЕ ВОПРОСЫ 38

ТЕМА 3 ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ 40

3.1 Основные принципы помехоустойчивого кодирования информации 40

3.2 Линейные блочные коды 41

3.2.1 Основные понятия двоичной арифметики 41

3.3 Код с проверкой на четность 42

3.4 Итеративный код 44

3.5 Способы задания линейных кодов. Порождающая матрица линейного блочного кода 45

3.6 Проверочная матрица линейного блочного кода 47

3.7 Синдром и обнаружение ошибки линейным блочным кодом 49

3.8 Синдромное декодирование линейных блочных кодов 50

3.9 Вес и расстояние Хэмминга. Способность кодов обнаруживать и исправлять ошибки 54

3.10 Код Хэмминга 56

^ КОНТРОЛЬНЫЕ ВОПРОСЫ 59

Список использованной и рекомендуемой литературы 62

ПРЕДИСЛОВИЕ



Предлагаемый конспект лекций представляет собой пособие по предмету “Теория информации”, который читается в Сумском государственном университете для студентов специальности “Информатика” заочной формы обучения.

Учебный курс рассматривает основные положения теории информации и кодирования и области их практического применения: сжатие информации и защита от помех.

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

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

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

В конце каждой темы приводится список контрольных вопросов для проведения индивидуальной проверки полученных знаний и умений.

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

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

ТЕМА 1 ОСНОВНЫЕ ПОЛОЖЕНИЯ ТЕОРИИ ИНФОРМАЦИИ

^

1.1 Предмет курса. Виды информации. Теорема дискретизации



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

При формальном представлении знаний каждому описываемому объекту ставится в соответствие числовой код, связи между объектами также представляются кодами. Для перевода неформальных данных в формальный цифровой вид используются специальные таблицы кодировки. Простейший пример такой таблицы – ASCII (American Standard Code for Information Interchange), которая сопоставляет печатным и управляющим символам числа от 0 до 127. Расширенный код ASCII+ описывает коды 256 символов: первые 128 совпадают со стандартным кодом, а дополнительные 128 определяются производителем оборудования и системного программного обеспечения.

Информация может быть двух видов: дискретная (цифровая) и непрерывная (аналоговая).

Непрерывная информация представляет собой непрерывный процесс изменения некоторой величины.

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

Дискретную информацию хранить и обрабатывать гораздо проще, так как она представляет последовательность чисел. В двоичной системе исчисления дискретная информация представлена последовательностью 0 и 1.





Рисунок 1.1


Одна позиция для двоичной цифры называется битом (bit, binary digit). Бит (б) – это наименьшая единица информации. Производные единицы: 1 Кб=210=1024 б; 1 Мб=220≈106 б; 1 Гб=230≈109 б; 1 Тб(тера)=240≈1012 б; 1 Пб(пета)=250≈1015 б.

Для перевода непрерывной информации в дискретную и наоборот используются специальные устройства модуляции/демодуляции – модемы. Скорость передачи информации измеряется в количестве переданных за одну секунду битов – бод (baud): 1 бод = 1 бит/с (bps).

Устройство, реализующее процесс дискретизации непрерывного сигнала, называется аналогово-цифровым преобразователем (АЦП, analog-to-digital converter, ADC). Частота, с которой АЦП производит замеры аналогового сигнала и выдает его цифровые значения, называется частотой дискретизации. Устройство, которое интерполирует дискретный сигнал до непрерывного, называется цифро-аналоговым преобразователем (ЦАП, digital-to-analogue converter, DAC).

Чем выше частота дискретизации, тем точнее перевод непрерывной информации в дискретный сигнал. Однако с ростом частоты растёт и размер дискретных данных и, следовательно, сложность обработки, передачи и хранения.

При всех качественных различиях между непрерывной и дискретной величинами существует жёсткая связь, устанавливаемая теоремой дискретизации Шеннона-Котельникова.

Как известно из математического анализа, любая непрерывная функция S(t) может быть разложена на конечном отрезке в ряд Фурье. Суть этого разложения состоит в том, что функция представляется в виде суммы ряда синусоид с различными амплитудами и фазами и с кратными частотами. Коэффициенты (амплитуды) при синусоидах называются спектром функции. У гладких функций спектр быстро убывает (с ростом номера коэффициенты быстро стремятся к нулю). Для «изрезанных» функций спектр убывает медленно, т.к. для представления резких изменений сигнала нужны синусоиды с большими частотами.

Считается, что сигнал имеет ограниченный спектр, если после определенного номера все коэффициенты спектра равны нулю. Другими словами, на заданном отрезке сигнал представляется в виде конечной суммы ряда Фурье. В этом случае говорят, что спектр сигнала лежит ниже граничной частоты fм, где fм частота синусоиды при последнем ненулевом коэффициенте ряда Фурье.


Теорема дискретизации формулируется следующим образом.


Непрерывная информация S(t) с ограниченным спектром, т.е. имеющая в своём спектре составляющие с частотами, не превышающими некоторую максимальную (граничную) частоту спектра fм, полностью определяет последовательностью отсчётов S(ti), взятых в дискретные моменты времени с шагом .


^

1.2 Базовые понятия теории информации



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


Кодирование – преобразование информации на упорядоченный набор символов, элементов, знаков. При кодировании каждому сообщению из некоторого множества (ансамбля) сообщений ставится в соответствие кодовая комбинация – набор символов (элементов, знаков).

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

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

Как безызбыточные, так и избыточные коды могут быть равномерные и неравномерные – с постоянным и переменным количеством разрядов.


Канал связи - это среда передачи информации, которая характеризуется максимально возможной для неё скоростью передачи данных – ёмкостью канала связи.

Ёмкость канала связи без шума можно приблизительно вычислить, зная максимальную частоту волновых процессов, допустимую в этом канале. Считается, что скорость передачи данных может быть не меньше этой частоты.

Типичные каналы связи: телеграфный, телефонный, оптоволоконный, цифровой телефонный. Наиболее широко используются телефонные линии связи, для которых достигнута скорость передачи данных больше 50 кбод.


Шум – это помехи в канале связи.


Обобщённая схема системы передачи информации показана на рис. 1.2.





Рисунок 1.2


^

1.3 Способы измерения информации



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

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

В основе теории информации лежит предложенный Клодом Шенноном способ измерения количества информации, содержащейся в одной случайной величине относительно другой случайной величины1. Этот способ приводит к выражению количества информации числом и даёт возможность объективно оценить информацию, содержащуюся в сообщении. Кратко рассмотрим вероятностный подход Шеннона к определению количества информации.

Пусть дискретный источник выдаёт последовательность сообщений xi, каждое из которых выбирается из алфавита сообщений x1, x2, …, xk, где kобъём алфавита.

В каждом элементарном сообщении для его получателя содержится информация как совокупность сведений о состоянии некоторой системы. Для того чтобы абстрагироваться от конкретного содержания информации, т.е. ее смыслового значения, и получить наиболее общее определение количества информации, количественную меру информации определяют без учёта её смыслового содержания, а также ценности и полезности для получателя.

До того как связь состоялась, имеется некоторая неопределённость относительно того, какое из сообщений из числа возможных будет передано. Степень неопределённости передачи хi можно определить его априорной вероятностью pi. Количество информации будет, таким образом, некоторой функцией от pi: I(Xi)=f(pi). Определим вид этой функции.

Будем считать, что мера количества информации I(Xi) должна удовлетворять двум интуитивным свойствам:

  1. если выбор сообщения источника xi заранее предопределён (нет неопределённости), т.е. речь идет о достоверном случае, вероятность которого pi=1 (точно произойдет), то I(Xi)=f(1)=0;

  2. если источник последовательно выдаёт сообщения xi и xj и вероятность такого выбора pij – совместная вероятность событий xi и xj, то количество информации в этих двух элементарных сообщениях равно сумме количества информации в каждом из них.

Вероятность совместного выпадения событий xi и xj определяется по закону умножения вероятностей


pij=pipj/i=PQ.


Тогда


I(Xi, Xj)=I(Xi)+I(Xj)=f(PQ)=f(P)+f(Q).


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


.


При этом коэффициент k и основание логарифма могут быть произвольными. Для того чтобы количество информации выражалось неотрицательным числом, принято k=-1, а основание логарифма чаще всего вбирают 2. Тогда


. (1.1)


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

Если источник информации выдает последовательность взаимозависимых сообщений, то получение каждого из них изменяет вероятность следующих и соответственно количество информации в них. В данном случае количество информации выражается через условную вероятность выбора источником сообщения xi при условии, что до этого были выбраны сообщения xi-1, xi-2, …, т.е

. (1.2)


Количество информации I(X) является случайной величиной, так как сами сообщения случайны. Распределение вероятностей I(X) определяется распределением вероятностей P(X) ансамбля сообщений источника.


Сам Шеннон однажды заметилError: Reference source not found, что смысл сообщений не имеет никакого отношения к его теории информации, которая целиком построена на положениях теории вероятности. Его способ измерения информации наводил на мысль о возможности существования способов измерения информации с учетом ее смыслового содержания - семантической информации.

Одной из таких мер информации является функция inf(S)=-log2p(S), где S – предложение, смысловое содержание которого измеряется; p(S) – вероятность истинности S. Свойства этой функции:

  1. если S1S2 истинно, то inf(S1) ≥ inf(S2);

  2. если S – истинно, то inf (S)=0;

  3. Inf (S) ≥ 0;

  4. Inf (S1, S2)= inf (S1) + inf(S2)p(S1, S2)= p(S1) +p(S2), т.е. S1, S2 независимы.


Пример: S1 = “a>3”, S2=“a=7”; S2 S1, inf(S2) > inf (S1).

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


^

1.4 Энтропия источника. Свойства количества информации и энтропии



Количество информации, содержащееся в одном элементарном сообщении xi, не полностью характеризует источник. Источник дискретных сообщений может быть охарактеризован средним количеством информации, приходящимся на одно элементарное сообщение, носящим название энтропия источника


, i=1…k , (1.3)


где k – объём алфавита сообщений.

Таким образом, энтропия – это среднестатистическая мера неопределенности знаний получателя информации относительно состояния наблюдаемого объекта.

В выражении (1.3) статистическое усреднение (т.е. определение математического ожидания дискретной случайной величины I(Xi)) выполняется по всему ансамблю сообщений источника. При этом необходимо учитывать все вероятностные связи между сообщениями. Чем выше энтропия источника, тем большее количество информации в среднем закладывается в каждое сообщение, тем труднее запомнить (записать) или передать такое сообщение по каналу связи. Таким образом, суть энтропии Шеннона заключается в следующем: энтропия дискретной случайной величин – это минимум среднего количества битов, которое нужно передавать по каналу связи о текущем значении данной случайной величины.

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


I(N)=NH(X).


Энтропия как количественная мера информационности источника обладает следующими свойствами:

  1. энтропия равна нулю, если хотя бы одно из сообщений достоверно (т.е. имеет вероятность pi=1);

  2. величина энтропии всегда больше или равна нулю, действительна и ограничена;

  3. энтропия источника с двумя альтернативными событиями может изменяться от 0 до 1;

  4. энтропия – величина аддитивная: энтропия источника, сообщения которого состоят из сообщений нескольких статистически независимых источников, равна сумме энтропий этих источников;

  5. энтропия будет максимальной, если все сообщения равновероятны


. (1.4)


При неравновероятных сообщениях xi энтропия уменьшается. В связи с этим вводят такую меру источника, как статистическая избыточность алфавита источника


, (1.5)


где H(X) – энтропия реального источника; H(X)max=log2k – максимально достижимая энтропия источника.

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


Существует также понятие семантической избыточности, которое следует из того, что любую мысль, которая содержится в сообщении из предложений человеческого языка, можно сформулировать короче. Считается, что если какое-либо сообщение можно сократить без потери его смыслового содержания, то оно имеет семантическую избыточность.


Рассмотрим дискретные случайные величины (д.с.в.) Х и Y, заданные законами распределения P(X=Xi)=pi, P(Y=Yj)=qj и совместным распределением P(X=Xi, Y=Yj)=pij. Тогда количество информации, содержащееся в д. с. в. Х относительно д. с. в. Y, определяется по формуле


. (1.6)


Для непрерывных случайных величин (сл. в.) X и Y, заданных плотностями распределения вероятностей X(t1), Y(t2) и XY(t1,t2), аналогичная формула имеет вид


.

Очевидно, что





следовательно


,


т.е. приходим к выражению (1.3) для расчета энтропии H(X).


Свойства количества информации и энтропии:

  1. I(X, Y) ≥ 0; I(X, Y)=0  X и Y независимые (одна случайная величина ничем не описывает другую);

  2. I(X, Y)=I(Y, X);

  3. НХ=0  X=const;

  4. I(X, Y)=HX+HY-H(X, Y), где ;

  5. I(X, Y) ≤ I(X, X); I(X, Y)= I(X, X)  X= f(Y).



^ КОНТРОЛЬНЫЕ ВОПРОСЫ


  1. Какие существуют виды информации?

  2. Как перевести непрерывную информацию в дискретный (цифровой) вид?

  3. Что такое частота дискретизации непрерывной информации?

  4. Как формулируется теорема дискретизации?

  5. Что такое информация, кодирование, канал связи, шум?

  6. В чем заключаются основные положения вероятностного подхода Шеннона к определению количества информации?

  7. Как определяется количество информации, содержащееся в одном сообщении дискретного источника?

  8. Как определяется количество информации на одно сообщение источника взаимозависимых сообщений?

  9. Что такое энтропия источника? Какие ее свойства?

  10. При каких условиях энтропия источника максимальна?

  11. Как определяется количество информации? Какие свойства количества информации?

  12. Чем обусловлена статистическая избыточность источника информации?
  1   2   3   4   5   6   7   8   9   10

Схожі:

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconКонспект лекций для студентов заочной формы обучения. Суми: СумДУ, 2007. 2
Тулякова Н. О. Теория информации: Конспект лекций для студентов заочной формы обучения. Суми: СумДУ, 2007
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconЕ. Е. Мандриченко Конспект лекций по дисциплине «Инженерная графика» (для студентов 1 курса заочной формы обучения направления подготовки 050701 «Электротехника и электротехнологии») Харьков хнагх 2011 Конспект
Конспект лекций по дисциплине «Инженерная графика» (для студентов 1 курса заочной формы обучения направления подготовки 050701 «Электротехника...
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconБ. И. Погребняк М. В. Булаенко
Конспект лекций для студентов 1-го курса дневной и заочной формы обучения образовательно-квалификационного уровня бакалавр, направления...
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconХарьковская национальная академия городского хозяйства о. М. Виноградская конспект лекций в схемах по дисциплине «организация труда менеджера»
Конспект лекций в схемах по дисциплине «Организация труда менеджера» (для студентов (для студентов 4 курса дневной и 3 курса заочной...
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconСадовников О. К., Фатеев Ю. А. Методические рекомендации для самостоятельной работы и выполнения контрольных работ по логике для студентов 1-2-го курсов заочной формы обучения направления подготовки 030601 «Менеджмент»
Для студентов 1-2-го курсов заочной формы обучения направления подготовки 030601 «Менеджмент», 020107 «Туризм», 140101 «Гостинично-ресторанное...
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconА. Г. Соболева конспект лекций по дисициплине «основы экономики транспорта»
Конспект лекций по дисциплине «Основы экономики транспорта» (для студентов 3 курса дневной и 4 курса заочной формы обучения направления...
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconВ. С. Шевченко Н. С. Виноградская конспект
Конспект лекций в схемах по дисциплине «Управление персоналом» (для студентов 5 курса направления подготовки 0502 “Менеджмент” специальности...
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconРабочая программа, методические указания и контрольные задания к изучению дисциплины «Коррозия и защита металлов» для студентов направления 0904 металлургия заочной формы обучения
«Коррозия и защита металлов» для студентов направления 0904 металлургия заочной формы обучения
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconРабочая программа, методические указания и контрольные задания к изучению дисциплины «Коррозия и защита металлов» для студентов направления 0904 металлургия заочной формы обучения
«Коррозия и защита металлов» для студентов направления 0904 металлургия заочной формы обучения
Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) Сумы, 2007 Содержание iconМетодические указания для выполнения лабораторных, самостоятельных и контрольных работ по курсу «Информатика и компьютерная техника»
«Информатика и компьютерная техника» (для студентов 1-го и 2-го курсов заочной формы обучения образовательно-квалификационного уровня...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи