Комбинаторная мера

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

Комбинаторная мера может использоваться для оценки информационных возможностей некоторого автомата, который способен генерировать дискретные сигналы (сообщения) в соответствии с определенным правилом комбинаторики. Пусть, например, есть автомат, формирующий двузначные десятичные целые положительные числа (исходное множество информационных элементов {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}). В соответствии с положениями комбинаторики, данный автомат генерирует размещения (различаются числа, например, 34 и 43) из 10 элементов (используются 10 цифр) по 2 (по условию задачи, формируются двузначные числа) с повторениями (очевидно, возможны числа, состоящие из одинаковых цифр, например, 33). Тогда можно оценить, сколько различных сообщений (двузначных чисел) может сформировать автомат, иначе говоря, можно оценить информационную емкость данного устройства: Р^п (₁₀²) = 10² = 100.

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

Пример 1. Определить емкость ASCII-кода, представленного в двоичной или шестнадцатеричной системе счисления.

ASCII-код – это сообщение, которое формируется как размещение с повторениями:

· для двоичного представления – из информационных элементов {0, 1}, сообщение длиной (объемом) 8 символов;

· для шестнадцатеричного представления – из информационных элементов {0, 1, 2, …., А, В, С, …. F}, сообщение длиной (объемом) 2 символа.

Тогда в соответствии с положениями комбинаторики:

I ^{(двоичное)} = Р^П(₂⁸) = 2⁸ = 256;

I ^{(шестнадцатеричное)} = Р^П(₁₆²) = 16² = 256,

где I ^{(двоичное)}, I ^{(шестнадцатеричное)} – количества информации, соответственно, для двоичного и шестнадцатеричного представления ASCII-кода.

Таким образом, емкость ASCII-кода для двоичного и шестнадцатеричного представления одинакова и равна 256.

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

В случае, когда сообщения формируются как размещения с повторениями из элементов алфавита мощности h и известно количество сообщений М, можно определить требуемый объем сообщения (т.е. его длину l) для того, чтобы в этом объеме представить все сообщения: l = log _h М.

Например, есть 4 сообщения – a, b, c, d. Выполняется двоичное кодирование этих сообщений кодом постоянной длины. Для этого требуются 2 двоичных разряда. В самом деле: l = log ₂ 4 = 2.

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

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

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