Комбинаторная мера используется для определения возможностей кодирующих систем в информационной технике

Кодирование сигнала

Кодирование сигнала – это его представление в определенной форме, удобной или пригодной для последующего использования сигнала. Говоря строже, это правило, описывающее отображение одного набора знаков в другой набор знаков. Тогда отображаемый набор знаков называется исходным алфавитом, а набор знаков, который используется для отображения, - кодовым алфавитом, или алфавитом для кодирования. При этом кодированию подлежат как отдельные символы исходного алфавита, так и их комбинации. Аналогично для построения кода используются как отдельные символы кодового алфавита, так и их комбинации. Например, дана таблица соответствия между натуральными числами трех систем счисления, аналогичная рассмотренной ранее. Эту таблицу можно рассматривать как некоторое правило, описывающее отображение набора знаков десятичной системы счисления в двоичную и шестнадцатеричную. Тогда исходный алфавит - десятичные цифры от 0 до 9, а кодовые алфавиты - это 0 и 1 для двоичной системы; цифры от 0 до 9 и символы {A, B, C, D, E, F} - для шестнадцатеричной.

Кодовой комбинацией, или, короче, кодом называется совокупность символов кодового алфавита, применяемых для кодирования одного символа (или одной комбинации символов) исходного алфавита. При этом кодовая комбинация может содержать один символ кодового алфавита. Исходным символом называется символ (или комбинация символов) исходного алфавита, которому соответствует кодовая комбинация. Например, поскольку 8 = 10002 и 8 является исходным символом, 1000 - это кодовая комбинация, или код, для числа 8. В то же время 8 - это исходный символ. Совокупность кодовых комбинаций называется кодом. Взаимосвязь символов (или комбинаций символов, если кодируются не отдельные символы) исходного алфавита с их кодовыми комбинациями составляет таблицу соответствия (или таблицу кодов).

Следует отметить, что понятие “код” омонимично: оно может употребляться и в смысле кодовой комбинации, и в приведенном выше смысле. Аналогично, понятие “кодовая комбинация” синонимично понятию “код”.

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

В зависимости от целей кодирования, различают следующие его виды:

1. кодирование по образцу - используется всякий раз при вводе информации в компьютер для ее внутреннего представления;

2. криптографическое кодирование, или шифрование, – используется, когда нужно защитить информацию от несанкционированного доступа;

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

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

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

Формула Шеннона позволяет определять также размер двоичного эффективного кода, требуемого для представления того или иного сообщения, имеющего определенную вероятность появления.

Пример 6. Есть 4 сообщения: a, b, c, d с вероятностями, соответственно, р(a) = 0,5; р(b) = 0,25; р(c) = 0,125; р(d) = 0,125. Определить число двоичных разрядов, требуемых для кодирования каждого их четырех сообщений.

В соответствии с формулой Шеннона имеем:

I(a) = -log₂0,5 = 2,

I(b) = -log₂0,25 = 2,

I(c) = -log₂0,125 = 3,

I(d) = -log₂0,125 = 3.

Пример 7. Определить размеры кодовых комбинаций для эффективного кодирования сообщений из примера 6.

Для вещественных значений объемов информации (что произошло в примере 1) в целях определения требуемого числа двоичных разрядов полученные значения округляются до целых по традиционным правилам арифметики. Тогда имеем требуемое число двоичных разрядов:

для сообщения об оценке 5 – 1,

для сообщения об оценке 4 – 2,

для сообщения об оценке 3 – 3,

для сообщения об оценке 2 – 3.

Проверим результат, построив эффективный код для сообщений об исходах экзамена методом Шеннона-Фано. Исходные данные – из примера 1. Имеем:

Исходные символы	Вероятности	Коды
Сообщение об оценке 5	0,5
Сообщение об оценке 4	0,25
Сообщение об оценке 3	0,125
Сообщение об оценке 2	0,125

Таким образом, задача решена верно.

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

где pi – вероятность i-го сообщения.

Пример 8. Определить среднее количество информации, получаемое студентом-хорошистом, по всем результатам сдачи экзамена.

В соответствии с приведенной формулой имеем:

Iср = - (0,5*log20,5 + 0,3*log20,3 + 0,1*log20,1 + 0,1*log20,1) = 1,67.

Пример 9. Определить среднее количество информации, получаемое нерадивым студентом, по всем результатам сдачи экзамена.

В соответствии с приведенной формулой имеем:

Iср = - (0,1*log20,1 + 0,2*log20,2 + 0,4*log20,4 + 0,3*log20,3) = 1,73.

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

Пусть у опыта два равновероятных исхода, составляющих полную группу событий, т.е. p1 = p2 = 0,5. Тогда имеем в соответствии с формулой для расчета I ср:

I ср = -(0,5*log20,5 + 0,5*log20,5) = 1.

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

Единица измерения информации при статистическом подходе – бит.

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

Семантический подход к измерению информации

Учитывает целесообразность и полезность информации. Применяется при оценке эффективности получаемой информации и ее соответствия реальности.

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

Целесообразность информации

Количество I получаемой вместе с сообщением информации с позиций ее целесообразности определяется по формуле:

где p1, p2 – вероятности достижения цели после и до получения сообщения, соответственно.

Пример 1. Пусть вероятность p2 сдачи экзамена по информатике до получения сообщения (подсказки от соседа) оценивается студентом со значением 0,2. После того, как ему удалось получить подсказку, вероятность сдачи увеличилась: p1 = 0,8. Определить количество информации, содержащейся в подсказке, с точки зрения ее целесообразности.

В соответствии с приведенной формулой имеем: I = log₂(0,8/0,2) = log₂4 = 2.

Пример 2. Пусть положение студента до получения подсказки оценивается аналогично предыдущему примеру. После получения подсказки, вопреки ожиданиям, вероятность сдачи еще уменьшилась, поскольку подсказка содержала неверную информацию: p1 = 0,1. Определить количество информации, содержащейся в подсказке, с точки зрения ее целесообразности.

В соответствии с приведенной формулой имеем: I = log₂(0,1/0,2) = log₂0,5 = -1.

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

Полезность информации

Количество усваиваемой потребителем информации Iусв тесно связано с теми знаниями, которые имеет потребитель к моменту получения информации – с тезаурусом (ТЗ) потребителя. Этим определяется полезность информации. В самом деле, для усвоения тех знаний, которые получаются в ВУЗе, требуется среднее образование - иначе студент ничего не поймет. С другой стороны, любая учебная дисциплина ориентируется на знания, которые учащийся должен приобрести в предыдущих курсах. Этим объясняется последовательность учебных дисциплин по годам обучения.

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

Как видно из графика, при тезаурусе, равном нулю и максимальному значению в точке max, информация не усваивается: в первом случае, потребителю непонятна принимаемая информация, во втором – она ему уже известна. Максимально усваивается информация (т.е. она наиболее полезна) в точке opt, когда потребитель обладает достаточным (но не максимально возможным) тезаурусом для понимания получаемой информации. При значении тезауруса i-го потребителя ТЗi количество усваиваемой им информации определяется как Iусв = f(ТЗi). Сам тезаурус ТЗi может быть практически определен как результат интеллектуального тестирования, которое проводится, например, в некоторых западных странах. При таком тестировании человеку выставляется некоторый балл, который и может расцениваться как его ТЗi.

Истинность информации

Эта мера оценивает информацию с позиций ее соответствия отображаемому источнику информации, т.е. реальному миру.

Пусть r(mess) – функция, оценивающая истинность сообщения mess как соответствие его реальному положению вещей: 0 ≤ r(mess) ≤ 1, причем при r(mess) = 1 сообщение истинно, а при r(mess) = 0 сообщение ложно.

Например, r(«данное пособие посвящено информатике») = 1, r(«данное пособие имеет объем 5 страниц») = 0.

Оценить истинность сложного сообщения можно, разбив его на простые. Например, сообщение mess:

«данное пособие посвящено информатике и имеет объем 5 страниц»

можно представить как два простых сообщения mess1 и mess2:

mess1 - «данное пособие посвящено информатике»,

mess2 - «данное пособие имеет объем 5 страниц».

Тогда можно предложить рассчитывать истинность сложного сообщения как среднее арифметическое значение истинностей сообщений, его составляющих (что называют - «истинно лишь наполовину»). В таком случае имеем:

r(mess) = Ѕ (r(mess1) + r(mess2)) = Ѕ (1 + 0) = 0,5.

Качество информации

Качество информации является одним из важнейших параметров для потребителя информации. Оно определяется следующими характеристиками:

1. репрезентативность – правильность отбора информации в целях адекватного отражения источника информации. Например, в целях большей репрезентативности данных о себе абитуриенты стремятся представить в приемную комиссию как можно больше свидетельств, дипломов, удостоверений и другой информации, подтверждающей их высокий уровень подготовки, что учитывается при зачислении в ВУЗ;

2. содержательность – семантическая емкость информации. Рассчитывается как отношение количества семантической информации к ее количеству в геометрической мере. Это характеристика сигнала, про который говорят, что «мыслям в нем тесно, а словам просторно». В целях увеличения содержательности сигнала, например, используют для характеристики успеваемости абитуриента не полный перечень его аттестационных оценок, а средний балл по аттестату;

3. достаточность (полнота) – минимальный, но достаточный состав данных для достижения целей, которые преследует потребитель информации. Эта характеристика похожа на репрезентативность, однако разница состоит в том, что в данном случае учитывается минимальный состав информации, который не мешает принятию решения. Например, абитуриент – золотой медалист может не представлять в приемную комиссию свой аттестат: диплом, подтверждающий получение золотой медали, свидетельствует о полном наборе отличных оценок в аттестате;

4. доступность – простота (или возможность) выполнения процедур получения и преобразования информации. Эта характеристика применима не ко всей информации, а лишь к той, которая не является закрытой. Для обеспечения доступности бумажных документов используются различные средства оргтехники для их хранения, а для облегчения их обработки используются средства вычислительной техники;

5. актуальность – зависит от динамики изменения характеристик информации и определяется сохранением ценности информации для пользователя в момент ее использования. Очевидно, что касается информации, которая используется при зачислении, она актуальна, так как само обучение уже закончилось, и его результаты изменены быть не могут, а, значит, остаются актуальными;

6. своевременность – поступление не позже заранее назначенного срока. Этот параметр также очевиден недавним абитуриентам: опоздание с представлением позитивной информации о себе при поступлении может быть чревато незачислением;

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

8. достоверность – свойство информации отражать источник информации с необходимой точностью. Эта характеристика вторична относительно точности. В предыдущем примере получаемая информация недостоверна;

9. устойчивость – способность информации реагировать на изменения исходных данных без нарушения необходимой точности.

Дата добавления: 2014-01-06