Переменное количество байтов

Переменное количество байтов В схеме VB переменное количество байтов зависит от размера интервала. Методы битового уровня адаптируют длину кода на уровне битов. Простейшим битовым кодом является унарный код (unary code). Унарный код числа п представляет собой строку, состоящую из п единиц, за которыми следует нуль. Очевидно, что это не очень эффективный код, но в свое время он нам пригодится.

Насколько эффективным может быть код в принципе? Предположим, что 2" интервалов G, где 1 < G < 2", являются равновероятными Тогда оптимальное кодирование для каждого интервала G должно использовать п битов. В таком случае некоторые интервалы (в данном случае — G= 2") невозможно закодировать с помощью менее чем log2 G бит. Наша цель — максимально приблизиться к нижней границе.

Метод, близкий к оптимальному, называется у-кодир&ванием (f encoding). Эта схема использует кодирование с переменной длиной с помощью разбиения интервала G на пару, состоящую из длины (length) и смещения (offset). Смещение представляет собой запись числа G в двоичном виде с удаленной ведущей единицей. Например, для числа 13 (бинарный код— 1101) смещение равно 101. Параметр длина кодирует длину смещения в унарном коде. Для числа 13 длина смещения равна 3 бит. В унарном коде это число выглядит как 1110. Следовательно, у-код числа 13 имеет вид 1110101. Он представляет собой конкатенацию длины 1110 и смещения 101.

Для того чтобы декодировать у-код, сначала необходимо прочитать унарный код, пока не будет обнаружен нуль, который его завершает, например четыре бита 1110 при расшифровке числа 1110101. Теперь нам известна длина смещения: 3 бит. После этого можно правильно считать смещение 101 и добавить единицу, удаленную при кодировании: 101 1101 = 13.

tel-icq