Я не получаю кодирование Golomb/Rice: он делает больше бит ввода или делает это?

В Golomb, или Rice, кодирование, вы разделили число N на две части, разделив его на другое число M и затем закодируйте целочисленный результат этого деления в унарном, а остаток в двоичном формате.

В Wikipedia example они используют 42 как N и 10 как M, поэтому мы получаем частное q из 4 (в унальном: 1110) и остаток r из 2 (в двоичном формате 010), так что полученное сообщение 1110,010 или 8 бит (запятая может быть пропущена). Простым двоичным представлением 42 является 101010 или 6 бит.

Мне кажется, это связано с унарным представлением q, которое всегда должно быть больше битов, чем двоичных.

Ясно, что я пропустил здесь несколько важных моментов. Что это?

Ответы

Ответ 1

Важным моментом является то, что коды Голомба не должны быть короче, чем кратчайшая двоичная кодировка для одного конкретного номера. Скорее, предоставляя определенный вид кодирование переменной длины, они уменьшают среднюю длину за кодированное значение по сравнению с кодировкой с фиксированной шириной, если закодированные значения взяты из большого диапазона, но наиболее распространенные значения обычно малы (и, следовательно, большую часть времени используют только небольшую часть этого диапазона).

В качестве примера, если вы должны были передавать целые числа в диапазоне от 0 до 1000, но большая часть фактических значений находилась в диапазоне от 0 до 10, при кодировании с фиксированной шириной большинство переданных кодов имел бы ведущие 0s, которые не содержат информации:

Чтобы охватить все значения от 0 до 1000, вам понадобится кодировка с 10-разрядным шифрованием в двоичном формате с фиксированной шириной. Теперь, поскольку большинство ваших значений будет ниже 10, по крайней мере первые 6 бит большинства чисел будут равны 0 и будут нести небольшую информацию.

Чтобы исправить это с помощью кодов Golomb, вы разбиваете числа, деля их на 10 и кодируя частное и остальное отдельно. Для большинства значений все, что должно быть передано, - это остаток, который может быть закодирован с использованием не более 4 битов (если вы используете усеченный двоичный код для остальных, это может быть меньше). Фактор затем передается в унальном, который кодируется как один бит 0 для всех значений ниже 10, как 10 для 10..19, 110 для 20..29 и т.д.

Теперь, для большинства ваших значений, вы уменьшили размер сообщения до 5 бит макс, но вы все равно можете передавать все значения однозначно без разделителей.

Это приводит к довольно высокой стоимости для больших значений (например, значения в диапазоне 990..999 нуждаются в 100 бит для частного), поэтому кодирование является оптимальным для двухсторонних геометрических распределений.

Длинные прогоны 1 бита в частных более крупных значениях могут быть решены с последующим кодированием длины. Однако, если факториалы потребляют слишком много места в полученном сообщении, это может указывать на то, что другие коды могут быть более подходящими, чем Golomb/Rice.

Ответ 2

Одно из различий между кодированием Golomb и двоичным кодом состоит в том, что двоичный код не является префиксным кодом, который является недействительным для кодирующих строк сколь угодно больших чисел (вы не можете решить, является ли 1010101010101010 конкатенацией 10101010 и 10101010 или что-то еще). Следовательно, они не так легко сопоставимы.

Во-вторых, код Голомба оптимален для геометрического распределения, в этом случае с параметром 2 ^ (- 1/10). Вероятность 42 составляет около 0,3%, поэтому вы получаете представление о том, насколько это важно для длины выходной строки.