Английская Википедия:Even–Rodeh coding

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Even–Rodeh code is a universal code encoding the non-negative integers developed by Shimon Even and Michael Rodeh.

Encoding

To code a non-negative integer Шаблон:Var in Even–Rodeh coding:

1. If Шаблон:Var is not less than 4 then set the coded value to a single 0 bit. Otherwise the coded value is empty.
2. If Шаблон:Var is less than 8 then prepend the coded value with 3 bits containing the value of Шаблон:Var and stop.
3. Prepend the coded value with the binary representation of Шаблон:Var.
4. Store the number of bits prepended in step 3 as the new value of Шаблон:Var.
5. Go back to step 2.

To decode an Even–Rodeh-coded integer:

1. Read 3 bits and store the value into Шаблон:Var.
   • If the first bit read was 0 then stop. The decoded number is Шаблон:Var.
   • If the first bit read was 1 then continue to step 2.
2. Examine the next bit.
   • If the bit is 0 then read 1 bit and stop. The decoded number is Шаблон:Var.
   • If the bit is 1 then read Шаблон:Var bits, store the value as the new value of Шаблон:Var, and go back to step 2.

Examples

Number	Encoding	Implied probability
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	Шаблон:Nowrap	1/1,048,576
︙

See also

• Elias omega (ω) coding