15.
Алгоритмический подход к оценке количества информации. Количество информации и
избыточность.
Выдвинутый
А.Н.Колмогоровым тезис о том, что наряду с уже признанным вероятностным
подходом к определению количества информации правомерны, а во многих ситуациях
и более естественны, иные подходы: комбинаторный и алгебраический, привел к
созданию нового раздела науки - алгоритмической теории информации.
При алгоритмическом
подходе учитываются не только все вероятностные закономерности, но и другие
(если они есть); если других закономерностей нет, то алгоритмический подход
приводит к тем же результатам, что и вероятностный. Алгоритмический подход
основан на применении теории алгоритмов для определения понятия энтропии, или
сложности, конечного объекта и понятия информации в одном конечном объекте о
другом. С помощью теории алгоритмов можно определить сложность описания
различных объектов. Так, по А.Н.Колмогорову "относительной
сложностью" объекта y при заданном x считается минимальная длина l(p)
"программы" p получения y из x. Сформулированное так определение
зависит от "метода программирования". Метод программирования есть не
что иное, как функция ф(р,x) = y ставящая в соответствие программе p и объекту
x объект y.
Избыточность
- введение в систему дополнительных компонентов сверх минимально необходимого
их числа с целью повышения надежности и работоспособности системы.
Следствием
ограничений на выбор источником знаков является недоиспользование их как
переносчиков инф-ии. Известная априорная? инф-ия о вероятностях выбора знакови их сочетаний приводят к уменьшению ср-й
неопределенности выбора источников знака, а следовательно, и переносимого им
кол-во инф-ии.
Мерой избыточности является величина D,
которая показывает, на сколько хорошо используются знаки данного источника.
Hmax(H) – считаем,
когда Рi равновероятностные события.
Lx – кол-во букв в
алфавите х.
D – Относительная
избыточность.
В двоичном
D2=1-H(x)/1=1-H(X)
Если избыточность источника равна 0, то формирование
им сообщений оптимально в смысле наибольшего количества переносимой инф-ии, и
мы можем подсчитать кол-во знаков, если нам известно кол-во инф-ии.
К=I/Hmax(x) знаков,
когда отсутствуют помехи.
Т.к. в реальных условиях энтропия сообщений
формируется источником, который обладает избыточностью всегда меньше
максимального (Hmax), то для передачи того же кол-ва инф-ии потребуется:
K2=I/H(x)>K1
знаков.
Поэтому говорят об избыточности знаков
сообщения и хар-ся тем же D;
D=(K2-K1)/K2=(Hmax(x)-H(x))/Hmax(x);
Полное устранение
избыточности позволит увеличить эффективность использования букв почти в 3
раза.
Избыточность также бывает:
1) Структурная –
дублирование каналов связи с определением принятой информации по мажоритарному
принципу.
2) Временная –
многократная передача данных, достоверность которых определяется либо по
мажоритарному, либо по статистическому принципу.
3) Функциональная –
передача данных с использованием обратной связи.
