Усеченное двоичное кодирование

Усеченное двоичное кодирование — это энтропийное кодирование, обычно используемое для равномерного распределения вероятностей с конечным алфавитом. Он параметризуется алфавитом с общим размером числа n . Это немного более общая форма двоичного кодирования , когда n не является степенью двойки .

Если n — степень двойки, то кодированное значение для 0 ≤ x < n — это простой двоичный код для x длины log ₂ ( n ). В противном случае пусть k = Floor(log ₂ ( n )), такое что 2 ^к < п < 2 ^{к +1} и пусть и = 2 ^{к +1} - н .

Усеченное двоичное кодирование присваивает первым u символам кодовые слова длины k , а затем присваивает оставшимся n - u символам последние n - u кодовые слова длины k + 1. Поскольку все кодовые слова длины k + 1 состоят из неназначенного кодового слова длины k с добавлением «0» или «1» результирующий код представляет собой префиксный код .

История

Используемые по крайней мере с 1984 года коды поэтапного внедрения , также известные как коды экономики , также известны как усеченное двоичное кодирование.

Пример с n = 5

Например, для алфавита {0, 1, 2, 3, 4}, n = 5 и 2 ² ≤ п < 2 ³ , следовательно, k = 2 и u = 2 ³ − 5 = 3. Усеченное двоичное кодирование присваивает первым u символам кодовые слова 00, 01 и 10, все длиной 2, затем присваивает последним n − u символам кодовые слова 110 и 111, последним двум кодовым словам длины 3.

Например, если n равно 5, простое двоичное кодирование и усеченное двоичное кодирование выделяют следующие кодовые слова . Показаны цифры ударил не передаются в усеченном двоичном формате.

Усечено двоичный	Кодирование			Стандартный двоичный
0	0	0	0	0
1	0	0	1	1
2	0	1	0	2
НЕ ИСПОЛЬЗУЕТСЯ	0	1	1	3
НЕ ИСПОЛЬЗУЕТСЯ	1	0	0	4
НЕ ИСПОЛЬЗУЕТСЯ	1	0	1	5/НЕ ИСПОЛЬЗУЕТСЯ
3	1	1	0	6/НЕ ИСПОЛЬЗУЕТСЯ
4	1	1	1	7/НЕ ИСПОЛЬЗУЕТСЯ

требуется 3 бита , следовательно, 2 Для кодирования n с использованием простого двоичного кодирования ³ − n = 8 − 5 = 3 не используются.

В числовом выражении, чтобы отправить значение x , где 0 ≤ x < n и где есть 2 ^к ≤ п < 2 ^{к +1} символов, имеется u = 2 ^{к +1} − n неиспользуемых записей, когда размер алфавита округляется до ближайшей степени двойки. Процесс кодирования числа x в усеченном двоичном формате таков: если x меньше u , закодируйте его в k двоичных битов; если x больше или равен u , закодируйте значение x + u в k + 1 двоичных битах.

Пример с n = 10

Другой пример: для кодирования алфавита размером 10 (от 0 до 9) требуется 4 бита, но есть 2 бита. ⁴ − 10 = 6 неиспользуемых кодов, поэтому для входных значений меньше 6 первый бит отбрасывается, а для входных значений, больших или равных 6, смещается на 6 до конца двоичного пространства. (Неиспользуемые шаблоны не показаны в этой таблице.)

Вход ценить	Компенсировать	Компенсировать ценить	Стандартный двоичный	Усечено двоичный
0	0	0	0 000	000
1	0	1	0 001	001
2	0	2	0 010	010
3	0	3	0 011	011
4	0	4	0 100	100
5	0	5	0 101	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

Вот более крайний случай: при n = 7 следующая степень двойки равна 8, поэтому k = 2 и u = 2. ³ − 7 = 1:

Вход ценить	Компенсировать	Компенсировать ценить	Стандартный двоичный	Усечено двоичный
0	0	0	0 00	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

Этот последний пример демонстрирует, что ведущий нулевой бит не всегда указывает на короткий код; если ты < 2 ^к , некоторые длинные коды начинаются с нулевого бита.

Простой алгоритм

Сгенерируйте усеченную двоичную кодировку для значения x , 0 ≤ x < n , где n > 0 — размер алфавита, содержащего x . n не обязательно должно быть степенью двойки.

string TruncatedBinary (int x, int n)
{
	// Set k = floor(log2(n)), i.e., k such that 2^k <= n < 2^(k+1).
	int k = 0, t = n;
	while (t > 1) { k++;  t >>= 1; }

	// Set u to the number of unused codewords = 2^(k+1) - n.
	int u = (1 << k + 1) - n;

	if (x < u)
        return Binary(x, k); 
    else
        return Binary(x + u, k + 1));
}

рутина Binary носит разъяснительный характер; обычно только самый правый len биты переменной x желательны. Здесь мы просто выводим двоичный код для x, используя len бит, при необходимости дополняя старшими нулями.

string Binary (int x, int len)
{
	string s = "";
	while (x != 0) {
		if (even(x))
            s = '0' + s;
		else  s = '1' + s;
		
		x >>= 1;
	}
	while (s.Length < len)
        s = '0' + s;
	return s;
}

Об эффективности

Если n не является степенью двойки и k -битные символы наблюдаются с вероятностью p , то ( k + 1)-битные символы наблюдаются с вероятностью 1 − p . Мы можем вычислить ожидаемое количество бит на символ. $b_{e}$ как

$b_{e}=pk+(1-p)(k+1).$

Необработанное кодирование символа имеет $b_{u}=k+1$ биты. Тогда относительная экономия места Коэффициент (см. сжатия данных ) при кодировании может быть определена как

$s=1-{\frac {b_{e}}{b_{u}}}=1-{\frac {pk+(1-p)(k+1)}{k+1}}.$

В упрощенном виде это выражение приводит к

$s={\frac {p}{k+1}}={\frac {p}{b_{u}}}.$

Это указывает на то, что относительная эффективность усеченного двоичного кодирования увеличивается по мере увеличения вероятности k p - битных символов и битовой длины символа необработанного кодирования. $b_{u}$ уменьшается.

См. также

• Закон Бенфорда
• Кодирование Голомба