Усеченное двоичное кодирование - это энтропийное кодирование, обычно используемое для равномерных распределений вероятностей с конечным алфавитом. Он параметризован алфавитом с общим размером числа n . Это немного более общая форма двоичного кодирования, когда n не является степенью двойки .
Если n является степенью двойки, то кодированное значение для 0 ≤ x < n является простым двоичным кодом для x длины log 2 ( n ). В противном случае пусть k = floor (log 2 ( n )) такое, что 2 k < n <2 k +1, и пусть u = 2 k +1 - n .
Усеченное двоичное кодирование назначает первым u символов кодовых слов длины k, а затем присваивает оставшимся n - u символам последние n - u кодовых слов длины k + 1. Поскольку все кодовые слова длины k + 1 состоят из неназначенного кодового слова длины k с добавленными «0» или «1» результирующий код является префиксным .
Пример с n = 5
Например, для алфавита {0, 1, 2, 3, 4} n = 5 и 2 2 ≤ n <2 3 , следовательно, k = 2 и u = 2 3 - 5 = 3. Усеченное двоичное кодирование присваивает первое u символов кодовых слов 00, 01 и 10, все длиной 2, затем назначает последним n - u символам кодовые слова 110 и 111, последние два кодовых слова длины 3.
Например, если n равно 5, простое двоичное кодирование и усеченное двоичное кодирование выделяют следующие кодовые слова . Показанные цифрыпораженный не передаются в усеченном двоичном формате.
Усеченный двоичный файл | Кодирование | Стандартный двоичный файл | ||
---|---|---|---|---|
0 | 0 | 0 | 0 | |
1 | 0 | 1 | 1 | |
2 | 1 | 0 | 2 | |
НЕ ИСПОЛЬЗУЕТСЯ | 3 | |||
НЕ ИСПОЛЬЗУЕТСЯ | 4 | |||
НЕ ИСПОЛЬЗУЕТСЯ | 5 / НЕ ИСПОЛЬЗУЕТСЯ | |||
3 | 1 | 1 | 0 | 6 / НЕ ИСПОЛЬЗУЕТСЯ |
4 | 1 | 1 | 1 | 7 / НЕ ИСПОЛЬЗУЕТСЯ |
Для кодирования n с использованием прямого двоичного кодирования требуется 3 бита , поэтому 2 3 - n = 8 - 5 = 3 не используются.
В числовом выражении, чтобы отправить значение x, где 0 ≤ x < n , и где есть 2 k ≤ n <2 k +1 символов, есть u = 2 k + 1 - n неиспользуемых записей, когда размер алфавита округляется в большую сторону. до ближайшей степени двойки. Процесс кодирования числа x в усеченном двоичном формате: Если x меньше u , закодировать его в k двоичных битах. Если x больше или равно u , кодируйте значение x + u в k + 1 двоичных битах.
Пример с n = 10
Другой пример, для кодирования алфавита размером 10 (от 0 до 9) требуется 4 бита, но есть 2 4 - 10 = 6 неиспользуемых кодов, поэтому входные значения меньше 6 имеют первый бит отбрасывается, а входные значения больше или равны до 6 смещены на 6 до конца двоичного пространства. (Неиспользуемые шаблоны не показаны в этой таблице.)
Входное значение | Компенсировать | Значение смещения | Стандартный двоичный | Усеченный двоичный |
---|---|---|---|---|
0 | 0 | 0 | 000 | |
1 | 0 | 1 | 001 | |
2 | 0 | 2 | 010 | |
3 | 0 | 3 | 011 | |
4 | 0 | 4 | 100 | |
5 | 0 | 5 | 101 | |
6 | 6 | 12 | 0110 | 1100 |
7 | 6 | 13 | 0111 | 1101 |
8 | 6 | 14 | 1000 | 1110 |
9 | 6 | 15 | 1001 | 1111 |
Для декодирования прочтите первые k бит. Если они кодируют значение меньше u , декодирование завершено. В противном случае считайте дополнительный бит и вычтите u из результата.
Пример с n = 7
Вот более крайний случай: при п = 7 следующая сила 2 : 8 так , к = 2 и у = 2 3 - 7 = 1:
Входное значение | Компенсировать | Значение смещения | Стандартный двоичный | Усеченный двоичный |
---|---|---|---|---|
0 | 0 | 0 | 00 | |
1 | 1 | 2 | 001 | 010 |
2 | 1 | 3 | 010 | 011 |
3 | 1 | 4 | 011 | 100 |
4 | 1 | 5 | 100 | 101 |
5 | 1 | 6 | 101 | 110 |
6 | 1 | 7 | 110 | 111 |
Этот последний пример демонстрирует, что начальный нулевой бит не всегда указывает на короткий код; если u <2 k , некоторые длинные коды будут начинаться с нулевого бита.
Простой алгоритм
Сгенерируйте усеченную двоичную кодировку для значения x , 0 <= x < n , где n > 0 - размер алфавита, содержащего x . n не обязательно должно быть степенью двойки.
строка TruncatedBinary (int x, int n){// Устанавливаем k = floor (log2 (n)), т.е. k такое, что 2 ^ k <= n <2 ^ (k + 1).int k = 0, t = n;в то время как (t> 1) {k ++; t >> = 1; }// Устанавливаем u равным количеству неиспользуемых кодовых слов = 2 ^ (k + 1) - n.int u = (1 << k + 1) - n;if (x )> иначе вернуть двоичный (x + u, k + 1));}
Процедура Binary носит пояснительный характер; обычно требуются только самые правые len бит переменной x . Здесь мы просто выводим двоичный код для x, используя len битов, при необходимости заполняя их старшими нулями.
строка Binary (int x, int len){строка s = "";while (x! = 0) {если (даже (x)) s = '0' + s;иначе s = '1' + s;х >> = 1;}while (s.Length)>return s;}
По эффективности
Если n не является степенью двойки и k битовых символов наблюдаются с вероятностью p , k + 1 битовых символов наблюдаются с вероятностью 1 - p . Мы можем рассчитать ожидаемое количество бит на символ в виде:
.
Исходное кодирование символа биты. Тогда относительная экономия пространства сек (см Data_compression_ratio ) о кодировании может быть определен как
.
В упрощенном виде это выражение приводит к:
.
Это указывает на то, что относительная эффективность усеченного двоичного кодирования увеличивается по мере увеличения вероятности p для k битовых символов, а количество битов исходного кодирования на символ уменьшается.