Кодирование Эвена – Родеха

Код Эвена-Родеха — универсальный код , кодирующий неотрицательные целые числа, разработанный Шимоном Эвеном и Майклом Родехом .

Кодирование

Чтобы закодировать неотрицательное целое число N в кодировании Эвена-Роде:

1. Если N не меньше 4, тогда задайте закодированное значение равным одному. 0 кусочек. В противном случае закодированное значение пусто.
2. Если N меньше 8, добавьте к закодированному значению 3 бита, содержащие значение N , и остановитесь.
3. Добавьте к закодированному значению двоичное представление N .
4. Сохраните количество битов, добавленных на шаге 3, как новое N. значение
5. Вернитесь к шагу 2.

Чтобы декодировать целое число, закодированное Эвеном-Роде:

1. значение в N. Прочитайте 3 бита и сохраните
   • Если первый прочитанный бит был 0 тогда остановись. Декодированное число N. —
   • Если первый прочитанный бит был 1 затем перейдите к шагу 2.
2. Изучите следующий бит.
   • Если бит 0 затем прочитайте 1 бит и остановитесь. Декодированное число N. —
   • Если бит 1 затем прочитайте N бит, сохраните значение как новое значение N и вернитесь к шагу 2.

Примеры

Число	Кодирование	Подразумеваемая вероятность
0	000	1/8
1	001	1/8
2	010	1/8
3	011	1/8
4	100 0	1/16
5	101 0	1/16
6	110 0	1/16
7	111 0	1/16
8	100 1000 0	1/256
9	100 1001 0	1/256
︙
15	100 1111 0	1/256
16	101 10000 0	1/512
︙
2761	100 1100 101011001001 0	1/1,048,576
︙

См. также

• Кодирование Элиаса омега (ω)