Длина смещения

Длина смещения Длина смещения (offset) равна Llog2 Gj бит, а длина параметра длина (length) равна Llog2 Gj + 1 бит. Таким образом, длина всего кода равна 2 х Llog2 Gj + 1 бит. Все у-коды имеют нечетную длину и всего в два раза больше длины оптимального кода, которая равна Llog2 G_|. Эго оптимальное значение определено на основе предположения, что все 2" интервалов от 1 до 2" являются равновероятными. Однако на практике это условие может не выполняться. Как правило, априори распределение вероятностей интервалов неизвестно.

Свойства дискретного распределения вероятностей  Р (включая то, является ли код оптимальным) характеризуются энтропией Н(Р), которая определяется следующим образом. н(р)=-^р(х)1оЕ2рЗдесь X — множество всех возможных чисел, которые необходимо закодировать (и следовательно. ^P(jc) = 1.0). Энтропия (entropy) — это мера неопределенности, что иллюстрирует рис. 5.9 для распределения вероятностей P среди двух исходов X = [х,, х2]. Энтропия достигает максимального уровня (Н(Р) = 1) при Р(х\) = Р(х2) = 0,5, когда неопределенность относительно того, какой из исходов х, будет следующим, является наибольшей. Минимальный уровень энтропии (Н(Р) = 0) достигается при Р(хх) = 0 и Р(х2) = 1, когда существует полная определенность.

Можно показать (см. библиографию), что при определенных условиях нижняя грани ца E(L) ожидаемой длины кода L равна Н(Р). Кроме того, можно доказать, что при условии 1 < Н(Р) < °° у-кодирование не больше чем в три раза отличается от оптимального, а при больших значениях Н(Р) этот показатель приближается к двум

Примечательно, что это соотношение сохраняется при любых распределениях вероятностей Р. Итак, даже не зная никаких свойств распределения интервалов, мы можем применять у-кодирование и быть уверенными, что при большой энтропии полученный код лишь примерно в два раза больше оптимального. Код, длина которого при произвольном распределении вероятностей Р отличается от оптимальной лишь на множитель, называется универсальным (universal).

tel-icq