ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.02.2021
Просмотров: 137
Скачиваний: 1
Количество
информации
Шенноновская
теория
информации
,
точнее
количества
информации
,
исходит
из
элементарного
альтернативного
выбора
между
двумя
знаками
(
битами
)
0
и
1
.
Такой
выбор
соответствует
приёму
сообщения
,
состоящего
из
одного
двоичного
знака
.
По
определению
,
количество
информации
,
содержащееся
в
таком
сообщении
,
принимается
за
единицу
и
также
называется
битом
.
Если
выбор
состоит
в
том
,
что
некоторый
знак
выбирается
из
множества
п
знаков
,
где
2
≥
n
,
то
это
можно
сделать
посредством
конечного
числа
следующих
друг
за
другом
альтернативных
выборов
в
форме
выборочного
каскада
:
данное
множество
из
n
знаков
разбивается
на
два
(
непустых
)
подмножества
,
каждое
из
которых
точно
так
же
разбивается
дальше
,
пока
мы
не
получим
одноэлементные
подмножества
.
При
заданном
выборочном
каскаде
нас
интересует
теперь
,
сколько
потребуется
альтернативных
выборов
для
выбора
какого
-
нибудь
определённого
знака
.
На
рис
.
3.1
приведён
пример
:
чтобы
выбрать
а
или
е
,
нужны
два
альтернативных
выбора
(
количество
информации
составляет
2
бита
);
чтобы
выбрать
b,
с
или
f,
необходимы
три
альтернативных
выбора
,
и
т
.
д
.
Если
некоторый
знак
встречается
часто
,
то
,
естественно
,
количество
выборов
,
требующихся
для
его
опознавания
,
стремятся
сделать
возможно
меньшим
.
Соответственно
для
опознавания
более
редких
знаков
приходится
использовать
большее
число
альтернативных
выборов
.
Другими
словами
,
часто
встречающиеся
знаки
содержат
малое
,
а
редкие
знаки
-
большое
количество
информации
.
Поэтому
представляется
разумным
разбивать
исходное
множество
знаков
не
на
равновеликие
,
а
на
равновероятные
подмножества
,
т
.
е
.
так
,
чтобы
при
каждом
разбиении
на
два
подмножества
суммы
вероятностей
для
знаков
одного
и
для
знаков
другого
подмножества
были
близки
друг
к
другу
,
насколько
это
возможно
.
a
b
c
e
f
g
d
a
e
c
b
f
d
g
a
b
d
g
e
c f
a
d
g
e
f
c
b
Рис
. 3.1
.
Выборочный
каскад
.
Ради
простоты
будем
считать
сначала
,
что
заданные
вероятности
позволяют
получить
точное
равенство
.
Тогда
если
i
-
й
знак
выделяется
после
ki
альтернативных
выборов
,
то
вероятность
его
появления
р
i
равна
)
2
/
1
(
k
i
.
Обратно
,
для
выбора
знака
,
который
встречается
с
вероятностью
р
i,
требуется
)
/
1
(
log
pi
k
i
i
=
альтернативных
выборов
.
Исходя
из
сказанного
,
мы
определим
количество
информации
,
содержащейся
в
знаке
,
задаваемое
частотой
появления
такого
знака
,
как
)
/
1
(
log
2
pi
[
бит
]
Тогда
среднее
количество
информации
,
приходящейся
на
один
произвольный
знак
,
будет
равно
)
1
(
log
2
p
p
H
i
i
⋅
=
∑
Это
-
основное
определение
теории
информации
Шеннона
.
Величину
Н
называют
средним
количеством
информации
на
знак
,
информацией
на
знак
или
энтропией
источника
сообщений
.
Тот
факт
,
что
для
затрат
на
выбор
существенным
является
не
количество
знаков
n
,
а
его
логарифм
,
в
экспериментальной
психологии
подтверждается
законом
Меркеля
(1885
г
.):
время
реакции
T
испытуемого
на
выполнение
задания
“
выбрать
определенный
предмет
из
n
имеющихся
”
растет
пропорционально
логарифму
от
n
n
T
log
180
200
2
⋅
+
=
[
мс
].
Результат
одного
отдельного
альтернативного
выбора
может
быть
представлен
как
0
или
1
.
Тогда
выбору
всякого
знака
соответствует
некоторая
последовательность
двоичных
знаков
0
и
1,
т
.
е
.
двоичное
слово
.
Мы
назовем
это
двоичное
слово
кодировкой
знака
,
а
множество
кодировок
всех
знаков
источника
сообщений
—
кодированием
источника
сообщений
.
Получающиеся
двоичные
слова
имеют
,
вообще
говоря
,
разную
длину
:
знаку
,
вероятность
которого
pi,
соответствует
слово
длины
)
/
1
(
log
2
pi
N
i
=
.
При
этом
автоматически
выполняется
свойство
префиксности
:
никакое
кодовое
слово
не
является
началом
другого
кодового
слова
.
Рассмотрим
пример
.
Буква
p
i
Двоичные
слова
a
1/4 00
e
1/4 01
f
1/8 100
c
1/8 101
b
1/8 110
d
1/16 1110
g
1/16 1111
Для
данного
множества
знаков
625
.
2
=
H
.
Можно
проверить
,
что
H
в
данном
примере
является
еще
и
средней
длиной
двоичных
слов
.
Если
при
некотором
кодировании
источника
сообщений
i
-
ый
знак
имеет
длину
N
i
,
то
средняя
длина
слов
равна
N
p
L
i
i
i
∑
=
В
случае
,
когда
набор
знаков
можно
разбить
на
точно
равновероятные
подмножества
,
достигается
строгое
равенство
H = L
.
Однако
в
общем
случае
,
имеет
место
неравенство
L
H
≤
.
Таким
образом
,
H
–
это
нижняя
граница
для
количества
затрачиваемых
альтернативных
выборов
при
наилучшем
возможном
кодировании
.
Если
проводить
кодирование
не
по
одному
символу
за
один
раз
,
а
строить
код
для
блоков
из
n
символов
(
расширения
кода
),
то
можно
рассчитывать
ближе
подойти
к
нижней
границе
для
средней
длины
.
Поскольку
вероятности
в
расширении
источника
более
разнообразны
,
чем
вероятности
исходного
источника
,
то
можно
ожидать
,
что
чем
выше
кратность
расширения
,
тем
более
эффективными
окажутся
коды
как
Хаффмена
,
так
и
коды
Фано
.
N
-
кратное
расширение
алфавита
источника
из
символов
s
i
с
заданными
вероятностями
p
i
состоит
из
символов
вида
s
s
s
i
i
i
n
,...,
,
2
1
с
вероятностями
pi
pi
pi
Q
n
i
...
2
1
=
.
Каждый
блок
из
n
первоначальных
символов
становится
одним
символом
t
i
с
вероятностью
Q
i
.
Все
вместе
они
образуют
алфавит
S
n
= T
.
Как
доказывается
в
[7],
средняя
длина
кодового
слова
для
n-
кратного
расширения
,
обладает
следующим
свойством
:
1
)
(
)
(
+
≤
≤
S
H
L
S
H
n
r
n
n
r
.
Если
данное
выражение
разделить
на
n
,
то
получится
средняя
длина
кодовой
последовательности
,
приходящейся
на
один
символ
исходного
алфавита
S
:
n
S
H
n
L
S
H
r
n
r
/
1
)
(
)
/
(
)
(
+
≤
≤
.
Последнее
выражение
составляет
суть
теоремы
Шеннона
о
кодировании
без
шума
:
для
n
-
кратного
расширения
достаточно
высокой
кратности
средняя
длина
кодового
слова
L
может
быть
сколь
угодно
близкой
к
H
r
(S)
.
Разность
L
-
Н
называют
избыточностью
кода
,
a
1
-
(H/L)
-
относительной
избыточностью
кода
.
Избыточность
-
это
мера
бесполезно
совершаемых
альтернативных
выборов
.
Так
как
в
практических
случаях
отдельные
знаки
почти
никогда
не
встречаются
одинаково
часто
,
то
кодирование
с
постоянной
длиной
кодовых
слов
в
большинстве
случаев
избыточно
.
Несмотря
на
это
,
такое
кодирование
применяют
довольно
часто
,
руководствуясь
техническими
соображениями
,
в
частности
возможностью
параллельной
и
мультиплексной
передачи
.
Определённую
избыточность
имеют
,
например
,
n
-
разрядные
двоичные
коды
для
отдельных
букв
русского
языка
.
Код
Морзе
уменьшает
эту
избыточность
.
Ещё
более
уменьшают
её
кодовые
словари
для
слов
целиком
.
Важной
практической
задачей
является
определение
энтропии
естественных
языков
.
Если
считать
,
что
в
русском
языке
все
33
буквы
и
пробел
равновероятны
,
то
при
34
знаках
мы
получим
09
.
5
34
log
2
=
≤
H
… [
бит
/
знак
].
Таблица
3.1.
Вероятности
отдельных
букв
в
русском
языке
.
Буква
p
i
Буква
p
i
пробел
0.175
я
0.018
о
0.090
ы
0.016
е
,
е
0.072
з
0.016
а
0.062
ь
,
ъ
0.014
и
0.062
б
0.014
т
0.053
г
0.013
н
0.053
ч
0.012
с
0.045
й
0.010
р
0.040
х
0.009
в
0.038
ж
0.007
л
0.035
ю
0.006
к
0.028
ш
0.006
м
0.026
ц
0.004
д
0.025
щ
0.003
п
0.023
э
0.003
у
0.021
ф
0.002
Если
же
учесть
частоты
букв
(
табл
. 3.1),
то
получим
35
.
4
≤
H
[
бит
/
знак
].
Однако
относительные
частоты
отдельных
букв
не
являются
статистически
независимыми
;
некоторые
,
например
,
в
русском
языке
ы
и
й
,
с
и
т
сильно
коррелируют
,
тогда
как
в
английском
языке
практически
нет
слов
,
в
которых
за
буквой
q
следует
какая
-
либо
буква
отличная
от
u
.
Если
учесть
ещё
и
относитель
-
ные
частоты
биграмм
и
триграмм
и
т
.
д
.,
то
значение
Н
снизится
ещё
больше
.
С
ростом
длины
статистически
учитываемых
групп
букв
мы
получаем
всё
лучшее
приближение
к
морфологически
корректному
,
но
семантически
бессмысленному
языку
(
рис
. 3.2).
Аналогично
можно
действовать
со
слогами
и
словами
.
Таким
способом
мы
получим
до
некоторой
степени
соответствующее
действительности
значение
19
.
1
≈
H
[
бит
/
знак
].
Отсюда
можно
вывести
,
что
относительная
избыточность
русского
литературного
языка
без
учета
семантики
составляет
по
меньшей
мере
76%.
Рис
. 3.2
.
Синтетический
язык
,
построенный
на
основе
относительных
частот
букв
.
По
относительной
частоте
отдельных
букв
ояраъиаеииеымроачднукет
ооант
оме
офтммюием
бчсин
амнз
мплид
енхаыюкиевеьннрвпьойунпмч
аащврям
харохоесншлтанарсмикнр
По
относительной
частоте
биграмм
аделосвасх
бы
икль
акорацетостмпрфовауациздетвелани
ванакстой
дадал
пиичаероме
ст
мычийспьзднадст
мых
иге
венорннфии
и
пьннислищиблямых
сыкостех
пь
цичнисл
мпоных
наслют
ны
гобору
кобостиянисиномаяз
По
относительной
частоте
триграмм
ымирогичнов
терет
рак
систическоможных
набот
бесстивание
этоты
и
высованечных
надание
алго
паставледсторы
уски
и
в
цие
систектуали
пархитикуслировычи
прехния
вкласты
областакженкравлятордиции
упробр
По
относительной
частоте
четырехбуквенных
сочетаний
наук
изучается
науки
баз
датчикомпьютерных
алгоритмов
польшого
информации
базы
данные
и
заправлениях
две
компьютера
живающимитирования
просы
релятся
компьютерными
взаимость
или
устройства
виде
с