Учебное пособие по информатике 2014. Основы информатики

• Название: Основы информатики
• Анкор: Учебное пособие по информатике 2014.pdf
• Дата: 28.03.2018
• Размер: 4.61 Mb.
• Имя файла: Учебное пособие по информатике 2014.pdf
• Тип: Учебное пособие; #17317
• страница: 2 из 28

1.2 Структурная мера информации
Информация всегда представляется в виде сообщения. Элементарная единица сообщений — символ. Символы, собранные в группы, — слова.
Сообщение, оформленное в виде слов или отдельных символов, всегда передается в материально-энергетической форме (электрический, световой, звуковой сигнал и т. д.).
Различают информацию непрерывную и дискретную.
Рисунок 1.2 – Способы представления информации
Функция x(t), изображенная на рисунке 1.2а, может быть представлена в непрерывном (рисунок 1.2б) и дискретном (рисунок 1.2в) видах. В непрерывном виде эта функция может принимать любые вещественные значения в данном диапазоне изменения аргумента t, т. е. множество значений непрерывной функции бесконечно. В дискретном виде функция x(t) может принимать вещественные значения только при определенных значениях аргумента. Какой бы малый интервал дискретности (т.е. расстояние между соседними значениями аргумента) не выбирался,
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
X
a
X
A
X
max
X
min
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
б
X
ц
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
в
X
1
X
2
X
7
X
3
X
6
X
5
X
4

13 множество значений дискретной функции для заданного диапазона изменений аргумента (если он не бесконечный) будет конечно (ограничено).
При использовании структурных мер информации учитывается только дискретное строение сообщения, количество содержащихся в нем информационных элементов, связей между ними. При структурном подходе различаются геометрическая, комбинаторная и аддитивная меры информации.
Геометрическая мера предполагает измерение параметра геометрической модели информационного сообщения (длины, площади, объема и т.п.) в дискретных единицах. Например, геометрической моделью информации может быть линия единичной длины (рисунок 1.3а – одноразрядное слово, принимающее значение 0 или 1), квадрат (рисунок 1.3б
— двухразрядное слово) или куб (рис 1.3в — трехразрядное слово).
Максимально возможное количество информации в заданных структурах определяет информационную емкость модели (системы), которая определяется как сумма дискретных значений по всем измерениям
(координатам).
Рисунок 1.3 – Геометрическая модель информации
В комбинаторной мере количество информации определяется как число комбинаций элементов (символов). Возможное количество информации совпадает с числом возможных сочетаний, перестановок и размещений элементов. Комбинирование символов в словах, состоящих только из 0 и 1, меняет значения слов. Рассмотрим две пары слов 100110 и 001101, 011101 и
111010. В них проведена перестановка крайних разрядов (изменено местоположение знакового разряда в числе — перенесен слева направо).
Аддитивная мера (мера Хартли), в соответствии с которой количество информации измеряется в двоичных единицах — битах (наиболее распространена). Вводятся понятия глубины q и длины n числа.
0
1 x
a
б
в
10
00
01
11
X
1
X
2
X
2
X
1
X
3
110
010
011
001
000
111
100
101

14
Глубина q числа – количество символов (элементов), принятых для
представления информации. В каждый момент времени реализуется только один какой-либо символ.
Длина n числа – количество позиций, необходимых и достаточных для
представления чисел заданной величины.
Далее понятие глубины числа будет трансформировано в понятие основания системы счисления. При заданных глубине и длине числа количество чисел, которое можно представить, N = q
n
. Величина N неудобна для оценки информационной емкости. Введем логарифмическую меру, позволяющую, вычислять количество информации — бит:
I(g)=log
2
N = n log
2
q (1.1)
Следовательно,
1 бит информации соответствует одному элементарному событию, которое может произойти или не произойти. Такая мера количества информации удобна тем, что она обеспечивает возможность оперировать мерой как числом. Количество информации при этом эквивалентно количеству двоичных символов 0 или 1. При наличии нескольких источников информации общее количество информации
I(q
1
, q
2
, …, q
k
) = I(q
1
) + I(q
2
)+ … + I(q
k
), (1.2) где I(q
k
) – количество информации от источника k.
Логарифмическая мера информации позволяет измерять количество информации и используется на практике.
1.3 Статистическая мера информации
В статистической теории информации вводится более общая мера количества информации, в соответствии с которой рассматривается не само событие, а информация о нем. Этот вопрос глубоко проработан К. Шенноном в работе «Избранные труды по теории информации». Если появляется сообщение о часто встречающемся событии, вероятность появления которого близка к единице, то такое сообщение для получателя малоинформативно.
Столь же малоинформативны сообщения о событиях, вероятность появления которых близка к нулю.
События можно рассматривать как возможные исходы некоторого опыта, причем все исходы этого опыта составляют ансамбль, или полную
группу событий. К. Шеннон ввел понятие неопределенности ситуации, возникающей в процессе опыта, назвав ее энтропией. Энтропия ансамбля есть количественная мера его неопределенности и, следовательно, информативности, количественно выражаемая как средняя функция множества вероятностей каждого из возможных исходов опыта.
Пусть имеется N возможных исходов опыта, из них k разных типов, а
i-й исход повторяется n
i раз и вносит информацию, количество которой оценивается как I
i
,. Тогда средняя информация, доставляемая одним опытом,
I
cp
= (n
1
I
1
+ n
2
I
2
+ … + n
k
I
k
)/N (1.3)

15
Но количество информации в каждом исходе связано с его вероятностью p
i
и выражается в двоичных единицах (битах) как I
i
=log
2
(1/p
i
)=
= –log
2
p
i
. Тогда
I
cp
= [n
1
(–log
2
p
1
) + … +n
k
(–log
2
p
k
)]/N (1.4)
Выражение (1.4) можно записать также в виде
I
cp
=
N
n
1
(–log
2
p
1
) +
N
n
2
(–log
2
p
2
)+ … +
N
n
k
(–log
2
p
1
) (1.5)
Отношения n/N представляют собой частоты повторения исходов, а следовательно, могут быть заменены их вероятностями n
i
/N=p
i
, поэтому их средняя информация в битах
I
cp
= p
1
(–log
2
p
1
) + … +p
k
(–log
2
p
k
)], или
I
cp
= –


k
i
i
p
1
log
2
p
i
= H . (1.6)
Полученную величину называют энтропией и обозначают обычно буквой Н. Энтропия обладает следующими свойствами:
1. Энтропия всегда неотрицательна, так как значения вероятностей выражаются величинами, не превосходящими единицу, а их логарифмы – отрицательными числами или нулем, так что члены суммы (1.6) – неотрицательны.
2. Энтропия равна нулю в том крайнем случае, когда одно из p
i
равно единице, а все остальные — нулю. Это тот случай, когда об опыте или величине все известно заранее и результат не дает новую информацию.
3. Энтропия имеет наибольшее значение, когда все вероятности равны между собой: p
1
= p
2
= ... = p
k
= 1/k . При этом
H = – log
2
(1/k) = log
2
k .
4. Энтропия объекта АВ, состояния которого образуются совместной реализацией состояний А и В, равна сумме энтропии исходных объектов А и
В, т. е. Н(АВ) = Н(А) + Н(В).
Если все события равновероятны и статистически независимы, то оценки количества информации, по Хартли и Шеннону, совпадают. Это свидетельствует о полном использовании информационной емкости системы.
В случае неравных вероятностей количество информации, по Шеннону, меньше информационной емкости системы. Максимальное значение энтропии достигается при р = 0,5 , когда два состояния равновероятны. При вероятностях р = 0 или р = 1, что соответствует полной невозможности или полной достоверности события, энтропия равна нулю.
Количество информации только тогда равно энтропии, когда неопределенность ситуации снимается полностью. В общем случае нужно считать, что количество информации есть уменьшение энтропии вследствие опыта или какого-либо другого акта познания. Если неопределенность снимается полностью, то информация равна энтропии: I = Н.
В случае неполного разрешения имеет место частичная информация, являющаяся разностью между начальной и конечной энтропией: I = H
1
–H
2

16
Наибольшее количество информации получается тогда, когда полностью снимается неопределенность, причем эта неопределенность была наибольшей – вероятности всех событий были одинаковы. Это соответствует максимально возможному количеству информации I
1
, оцениваемому мерой
Хартли:
I
1
= log
2
N = log
2
(1/p) = –log
2
p , где N — число событий; р — вероятность их реализации в условиях равной вероятности событий.
Таким образом, I
1
= H
max
Абсолютная избыточность информации D
абс представляет собой разность между максимально возможным количеством информации и энтропией: D
абс
= I
1
– H , или D
абс
= H
max
– H .
Пользуются также понятием относительной избыточности
D = (H
max
– H)/H
max
(1.7)
1.4 Семантическая мера информации
Вычислительные машины обрабатывают и преобразуют информацию разного содержания — от числовых данных до сочинения музыки и стихов.
Вся эта информация изображается соответствующими символами. Оценка содержания разнохарактерной информации — весьма сложная проблема.
Среди семантических мер наиболее распространены содержательность, логическое количество, целесообразность и существенность информации.
Содержательность события выражается через функцию меры m(i) – содержательности его отрицания. Оценка содержательности основана на математической логике, в которой логические функции истинности m(i) и ложности m(

i ) имеют формальное сходство с функциями вероятностей события p(i) и антисобытия q(i) в теории вероятностей.
Как и вероятность, содержательность события изменяется в пределах
0

m(i)

1.
Логическое количество информации I
nf
, сходное со статистическим количеством информации, вычисляется по выражению:
I
nf
= log
2
[1/m(i)] = –log
2
m(

i ) .
Отличие статистической оценки от логической состоит в том, что в первом случае учитываются вероятности реализации тех или иных событий, что приближает к оценке смысла информации.
Если информация используется в системах управления, то ее полезность целесообразно оценивать по тому эффекту, который она оказывает на результат управления.
Мера целесообразности информации определяется как изменение вероятности достижения цели при получении дополнительной информации.
Полученная информация может быть пустой, т. е. не изменять вероятности достижения цели, и в этом случае ее мера равна нулю. В других случаях полученная информация может изменять положение дела в худшую сторону,

17 т.е. уменьшить вероятность достижения цели, и тогда она будет дезинформацией, измеряющейся отрицательным значением количества информации. Наконец, в благоприятном случае получается добротная информация, которая увеличивает вероятность достижения цели и измеряется положительной величиной количества информации.
Мера целесообразности в общем виде может быть аналитически выражена в виде соотношения
I
цел
= log
2
p
1
– log
2
p
0
= log
2 0
1
p
p
, (1.8) где p
0
и p
1
– начальная (до получения информации) и конечная (после получения информации) вероятности достижения цели.
Следует различать существенность самого события; существенность времени совершения события или его наблюдения (рано—поздно—момент); существенность координаты совершения события.
Измерение некоторого параметра X можно характеризовать несколькими функциями величины х: вероятностью р(х), погрешностью измерения

(х) и существенностью с(х). Каждой из этих функций можно поставить в соответствие определенную меру информации. Мерой Хартли оценивается функция погрешности

при фиксированных значениях функции вероятности (р = const) и существенности (с = const). Мерой Шеннона оценивается функция вероятности (р = var) при фиксированных значениях функций погрешности (

= const) и существенности (с = const) . Мера существенности относится к ситуации с фиксированными функциями погрешности (

= const) и вероятности (р = const) . Можно ввести функции существенности: с
х
, зависящие от х; с
T
, c
N
, зависящие от времени Т и пространства (канала) N.
1.5 Преобразование информации
Информационное сообщение всегда связано с источником информации, приемником информации и каналом передачи.
Дискретные сообщения состоят из конечного множества элементов, создаваемых источником последовательно во времени. Набор элементов
(символов) составляет алфавит источника.
Непрерывные сообщения задаются какой-либо физической величиной, изменяющейся во времени. Получение конечного множества сообщений за конечный промежуток времени достигается путем дискретизации (во времени), квантования (по уровню) (см. рисунок 1.2).
В большинстве случаев информация о протекании того или иного физического процесса вырабатывается соответствующими датчиками в виде сигналов, непрерывно изменяющихся во времени. Переход от аналогового представления сигнала к цифровому дает в ряде случаев значительные преимущества при передаче, хранении и обработке информации.
Преобразование осуществляется с помощью специальных устройств –

18 преобразователей непрерывных сигналов и может быть выполнено дискретизацией во времени и квантованием по уровню.
Рассмотрим разновидности сигналов, которые описываются функцией
x(t).
1. Непрерывная функция непрерывного аргумента. Значения, которые могут принимать функция x(t) и аргумент t, заполняют промежутки (x
min
, x
max
) и (-T, T) соответственно.
2. Непрерывная функция дискретного аргумента. Значения функции
x(t) определяются лишь на дискретном множестве значений аргумента t
i
,
i=0

1

2, … Величина x(t
i
) может принимать любое значение в интервале
(x
min
, x
max
).
3. Дискретная функция непрерывного аргумента. Значения, которые может принимать функция x(t), образуют дискретный ряд чисел х
1
, х
2
,..., x k
Значение аргумента t может быть любым в интервале (-Т, Т).
4. Дискретная функция дискретного аргумента. Значения, которые могут принимать функция х(t) и аргумент t, образуют дискретные ряды чисел x
1
, x
2
, ..., x k
и t
1
, t
2
, ..., t k
, заполняющие интервалы (x
min
, x
max
) и (-Т,Т) соответственно.
Первая из рассмотренных разновидностей принадлежит непрерывным сигналам, вторая и третья — дискретно-непрерывным, а четвертая — дискретным сигналам.
Операцию, переводящую информацию непрерывного вида в информацию дискретного вида, называют квантованием по времени, или
дискретизацией. Следовательно, дискретизация состоит в преобразовании сигнала x(t) непрерывного аргумента t в сигнал x(t
i
) дискретного аргумента t
i
Квантование по уровню состоит в преобразовании непрерывного множества значений сигнала x(t
i
) в дискретное множество значений x
k
, k =
=0,1,..., (m - 1); x
k

(x
min
, x
max
) (третий вид сигнала).
Совместное применение операций дискретизации и квантования по уровню позволяет преобразовать непрерывный сигнал x(t) в дискретный по координатам х и t (четвертая разновидность).
В результате дискретизации исходная функция x(t) заменяется совокупностью отдельных значений x(t
i
). По значениям функции x(t
i
) можно восстановить исходную функцию x(t) с некоторой погрешностью. Функцию, полученную в результате восстановления (интерполяции) по значениям x(t
i
), будем называть воспроизводящей и обозначать V(t).
При дискретизации сигналов приходится решать вопрос о том, как часто следует проводить отсчеты функции, т. е. каков должен быть шаг дискретизации

t
i
= t
i
– t
i-1
. При малых шагах дискретизации количество отсчетов функции на отрезке обработки будет большим и точность воспроизведения — высокой. При больших шагах дискретизации количество отсчетов уменьшается, но при этом, как правило, снижается точность восстановления. Оптимальной является такая дискретизация, которая обеспечивает представление исходного сигнала с заданной точностью при минимальном количестве отсчетов.

19
Методы дискретизации и восстановления информации классифицируются в зависимости от регулярности отсчета, критерия оценки точности дискретизации и восстановления, вида базисной функции, принципа приближения.
Регулярность отсчета определяется равномерностью дискретизации.
Дискретизация называется равномерной (рисунок 1.4а), если длительность интервалов

t
i
= const на всем отрезке обработки сигнала.
Методы равномерной дискретизации широко применяют, так как алгоритмы и аппаратура для их реализации достаточно просты. Однако при этом возможна значительная избыточность отсчетов.
Дискретизация называется неравномерной (рисунок 1.4б), если длительность интервалов между отсчетами

t
i
, различна, т. е.

t
i
= var .
Выделяют две группы неравномерных методов: адаптивные и программируемые. При адаптивных методах интервалы

t
i
, изменяются в зависимости от текущего изменения параметров сигналов. При программируемых методах интервалы

t
i
, изменяются либо оператором на основе анализа поступающей информации, либо в соответствии с заранее установленной программой работы.
Рисунок 1.4 – Способы дискретизации информации
Критерии оценки точности дискретизации сигнала выбираются получателем информации и зависят от целевого использования сигнала и возможностей аппаратной (программной) реализации. Чаще других используются критерий наибольшего отклонения, среднеквадратический, интегральный и вероятностный.
Тип базисных (приближающих, воспроизводящих) функций в основном определяется требованиями ограничения сложности устройств
(программ) дискретизации и восстановления сигналов.
Воспроизводящие функции v(t) обычно совпадают с приближающими функциями p(t), хотя в общем случае они могут отличаться друг от друга.
Чаще всего для дискретизации и восстановления используют ряды Фурье и
Котельникова, полиномы Чебышева и Лежандра, степенные полиномы, функции Уолша и Хаара, гипергеометрические функции.
X
X
t
1
t
2
t
3
t
4
t
5
t
6
t
a
б
t
1
t
2
t
3
t
4
t
5
t
6
t
∆t
∆t

20
При равномерной дискретизации шаг

t и частота отсчетов F
0
— постоянные величины (рисунок 1.4а). Модель равномерной дискретизации очень хорошо подходит к модели синхронных автоматов. Теорема
Котельникова позволяет осуществлять выбор шага дискретизации, что существенным образом может повлиять на количество и скорость поступления информации для обработки.
Рисунок 1.5 – Квантование по уровню
Квантование по уровню состоит в преобразовании непрерывных значений сигнала x(t
i
) в моменты отсчета t
i
, в дискретные значения (рисунок
1.5). В соответствии с графиком изменения функции x(t) ее истинные значения представляются в виде заранее заданных дискретных уровней 1, 2,
3, 4, 5 или 6. Функция в моменты отсчета может задаваться или точно
(значение х
2
– уровень 4), или с некоторой погрешностью (значение х
1
— уровень 2, значение x
3
— уровень 6).
Квантование по уровню может быть равномерным и неравномерным в зависимости от величины шага квантования. Под шагом (интервалом) квантования

m
понимается разность

m
= x
m
– x
m-1
, где x
m
, x
m-1
– соседние уровни квантования.
Уровень квантования для заданного значения сигнала x(t) можно выразить двумя способами:
1)
сигнал x(t
i
) отождествляется с ближайшим уровнем квантования;
2)
сигнал x(t
i
) отождествляется с ближайшим меньшим (или большим) уровнем квантования.
Так как в процессе преобразования значение сигнала x(t) отображается уровнем квантования x
m
, а каждому уровню m может быть поставлен в соответствие свой номер (число), то при передаче или хранении информации можно вместо истинного значения величины
x
m
использовать соответствующее число m. Истинное значение уровня квантования легко восстановить, зная масштаб по шкале х. Для представления m уровней квантования с помощью неизбыточного равномерного кода потребуется
n=log
2
m разрядов. Такое преобразование сопровождается шумами или погрешностью квантования. Погрешность квантования связана с заменой истинного значения сигнала x(t
i
) значением, соответствующим уровню
1
2
3
4
5
6
X
X
1
X
2
X
3
t
i-1
t
i
t
i+1
t

21 квантования x
m
. Максимальная погрешность квантования зависит от способа отождествления сигнала с уровнем квантования. Для первого из рассмотренных способов она равна 0,5

m
, для второго –

m
Чем меньше шаг квантования, тем меньше погрешность квантования.
Можно принять, что погрешность квантования в пределах шага квантования имеет равновероятный закон распределения, т. е. любое значение функции в пределах шага будет равновероятным.
Наиболее часто используются степенные алгебраические полиномы вида V(t)=


n
i
i
i
t
a
0
, где n — степень полинома, а
i
— действительные коэффициенты. Из этого класса функций наиболее полно исследовано применение полиномов нулевой и первой степени. Алгебраические полиномы удобны для программирования и обработки на ЭВМ.
Выбор оптимальной функции представляет определенные трудности, так как при решении задачи минимизации числа дискретных характеристик для описания сигнала с заданной точностью должны учитывать сложность аппаратуры (программ), допустимое время задержки в выдаче информации и другие факторы.
Метод дискретизации при преобразовании непрерывной информации в дискретную влияет на количество информации, которую надо хранить или преобразовывать в ЭВМ. Важна теорема Котельникова, согласно которой функция, имеющая ограниченный спектр частот, полностью определяется дискретным множеством своих значений, взятых с частотой отсчетов:
F
0
= 2f
m
, (1.9) где f
m
= 2

m
– максимальная частота в спектре частот S(j

) сигнала x(t);

m
–
угловая скорость.
Функция x(t) воспроизводится без погрешностей по точным значениям
x(t
i
) в виде ряда Котельникова:
,
)
(
)
(
sin
)
(
)
(
0
t
t
m
k
t
k
t
k
t
k
x
t
x










(1.10) где

t – шаг дискредитации.
Теорема Котельникова справедлива для сигналов с ограниченным спектром. Реальные сигналы — носители информации — имеют конечную длительность. Спектр таких сигналов не ограничен, т. е. реальные сигналы не соответствуют в точности модели сигнала с ограниченным спектром, и применение теоремы Котельникова к реальным сигналам связано с погрешностями при восстановлении сигналов по формуле (1.10) и неопределенностью выбора шага дискретизации или частоты отсчетов.
Для практических задач, однако, идеально точное восстановление функций не требуется, необходимо лишь восстановление с заданной точностью. Поэтому теорему Котельникова можно рассматривать как приближенную для функций с неограниченным спектром. На практике частоту отсчетов часто определяют по формуле
F
0
= 2f
max
k
3
, (1.11)

22 где k
3
— коэффициент запаса (обычно 1,5 < k
3
< 6 ); f
max
— максимальная допустимая частота в спектре сигнала x(t), например, с учетом доли полной энергии, сосредоточенной в ограниченном частотой спектре сигнала.
Из вышеизложенного следует, что преобразование непрерывной информации в дискретную может сопровождаться сжатием информации
(уменьшением ее количества). Квантование по уровню — один из способов сжатия информации.
Квантование и дискретизация находят широкое применение в преобразователях информации, используемых при связи ЭВМ с конкретными объектами (процессами).