Even–Rodeh coding: Difference between revisions

Revision as of 14:28, 21 February 2020

Revision as of 14:30, 21 February 2020

Line 1:

'''Even-RodehEven–Rodeh code''' is a [[Universal code (data compression)|universal code]] encoding the non-negative integers developed by [[Shimon Even]] and [[Michael Rodeh]].<ref name="EvenRodeh"/>

== Encoding ==

To code a [[non-negative integer]] ''{{var|N''}} in Even-RodehEven–Rodeh coding:

# If ''{{var|N''}} is not less than 4 then set the coded value to a single <code>0</code> bit. Otherwise the coded value is empty.

# If ''{{var|N''}} is less than 8 then prepend the coded value with 3 bits containing the value of ''{{var|N''}} and stop.

# Prepend the coded value with the [[binary numeral system|binary]] representation of ''{{var|N''}}.

# Store the number of bits prepended in step 3 as the new value of ''{{var|N''}}.

# Go back to step 2.

To decode an Even-RodehEven–Rodeh-coded integer:

# Read 3 bits and store the value into ''{{var|N''}}.

#* If the first bit read was <code>0</code> then stop. The decoded number is ''{{var|N''}}.

#* If the first bit read was <code>1</code> then continue to step 2.

# Examine the next bit.

#* If the bit is <code>0</code> then read 1 bit and stop. The decoded number is ''{{var|N''}}.

#* If the bit is <code>1</code> then read ''{{var|N''}} bits, store the value as the new value of ''{{var|N''}}, and go back to step 2.

== Examples ==